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
Computer has a single FIFO queue of ?xed precision unsigned integers with the length of the queue unbounded. You can use access methods similar to those in the third model. In this


A problem is said to be unsolvable if no algorithm can solve it. The problem is said to be undecidable if it is a decision problem and no algorithm can decide it. It should be note

What are the benefits of using work breakdown structure, Project Management


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

The universe of strings is a very useful medium for the representation of information as long as there exists a function that provides the interpretation for the information carrie

One might assume that non-closure under concatenation would imply non closure under both Kleene- and positive closure, since the concatenation of a language with itself is included

Since the signi?cance of the states represented by the nodes of these transition graphs is arbitrary, we will allow ourselves to use any ?nite set (such as {A,B,C,D,E, F,G,H} or ev

how many pendulum swings will it take to walk across the classroom?