Strictly local generation automaton, Theory of Computation

Another way of interpreting a strictly local automaton is as a generator: a mechanism for building strings which is restricted to building all and only the

automaton as an inexhaustible set of tiles labeled with the pairs of symbols, infinitely many instances of each type. The generator starts by selecting any tile labeled with 'x' on its left half. It then proceeds by selecting any tile for which the left half symbol matches the symbol on the right half of the previously selected tile and placing it with its left half overlapping the right half of that previous tile. In this way, the sequence of tiles grows until some tile with 'x' on its right half is placed. The generated string is the sequence of exposed symbols, not including the beginning and end symbols. Generation is non-deterministic-at each step the choice of tile is restricted only by the right symbol of the previous tile. A derivation of the generator is just the sequence of choices it makes in assembling a string, a sequence of pairs of symbols. The language generated by the generator is the set of all strings assembled by any of its derivations.

It should be clear that every string assembled by a derivation of the generator will be accepted by the automaton: the computation of the automaton will check the same sequence of pairs as the derivation of the generator uses and each of those pairs will be in the lookup table, hence, the computation will accept. Similarly it should be clear that every string accepted by a computation of the automaton will be assembled by the corresponding derivation of the generator.

Posted Date: 3/21/2013 6:06:47 AM | Location : United States

Related Discussions:- Strictly local generation automaton, Assignment Help, Ask Question on Strictly local generation automaton, Get Answer, Expert's Help, Strictly local generation automaton Discussions

Write discussion on Strictly local generation automaton
Your posts are moderated
Related Questions
Exercise:  Give a construction that converts a strictly 2-local automaton for a language L into one that recognizes the language L r . Justify the correctness of your construction.

For every regular language there is a constant n depending only on L such that, for all strings x ∈ L if |x| ≥ n then there are strings u, v and w such that 1. x = uvw, 2. |u

To see this, note that if there are any cycles in the Myhill graph of A then L(A) will be infinite, since any such cycle can be repeated arbitrarily many times. Conversely, if the

A context free grammar G = (N, Σ, P, S)  is in binary form if for all productions A we have |α| ≤ 2. In addition we say that G is in Chomsky Normaml Form (CNF) if it is in bi

State & prove pumping lemma for regular set. Show that for the language L={ap |p is a prime} is not regular

design a turing machine that accepts the language which consists of even number of zero''s and even number of one''s?

Application of the general suffix substitution closure theorem is slightly more complicated than application of the specific k-local versions. In the specific versions, all we had

If the first three words are the boys down,what are the last three words??

This was one of the ?rst substantial theorems of Formal Language Theory. It's maybe not too surprising to us, as we have already seen a similar equivalence between LTO and SF. But

Our DFAs are required to have exactly one edge incident from each state for each input symbol so there is a unique next state for every current state and input symbol. Thus, the ne