Defining strictly local automata, Theory of Computation

One of the first issues to resolve, when exploring any mechanism for defining languages is the question of how to go about constructing instances of the mechanism which define particular, given languages. Towards that end, note that a strictly 2-local automaton can require a particular symbol to appear at the beginning or end of the string and it can permit particular pairs of symbols to occur in the interior of the string but, in general, it can't require an arbitrary pair of symbols to occur in the interior of the string. Consider, for example the language:

639_De?ning Strictly Local Automata.png

This is just the set of all strings over {a, b} in which the sequence ‘ab' occurs at least once. Since the string aabaa is in L1, any strictly 2-local automaton will have to include at least the pairs:

fia, aa, ab, ba, afi.

But then the string aaaaa will also be accepted, using just the first two and the last one of these pairs. Roughly, as long as we have to permit other pairs starting with ‘a' we cannot require ‘ab' to occur.

Posted Date: 3/21/2013 5:51:00 AM | Location : United States

Related Discussions:- Defining strictly local automata, Assignment Help, Ask Question on Defining strictly local automata, Get Answer, Expert's Help, Defining strictly local automata Discussions

Write discussion on Defining strictly local automata
Your posts are moderated
Related Questions

Strictly 2-local automata are based on lookup tables that are sets of 2-factors, the pairs of adjacent symbols which are permitted to occur in a word. To generalize, we extend the

Distinguish between Mealy and Moore Machine? Construct a Mealy machine that can output EVEN or ODD According to the total no. of 1's encountered is even or odd.

can you plz help with some project ideas relatede to DFA or NFA or anything

i want to do projects for theory of computation subject what topics should be best.

When we say "solved algorithmically" we are not asking about a speci?c programming language, in fact one of the theorems in computability is that essentially all reasonable program

We will specify a computation of one of these automata by specifying the pair of the symbols that are in the window and the remainder of the string to the right of the window at ea

Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

Computer has a single LIFO stack containing ?xed precision unsigned integers (so each integer is subject to over?ow problems) but which has unbounded depth (so the stack itself nev

Can you say that B is decidable? If you somehow know that A is decidable, what can you say about B?