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
Myhill graphs also generalize to the SLk case. The k-factors, however, cannot simply denote edges. Rather the string σ 1 σ 2 ....... σ k-1 σ k asserts, in essence, that if we hav

As we are primarily concerned with questions of what is and what is not computable relative to some particular model of computation, we will usually base our explorations of langua

The fundamental idea of strictly local languages is that they are speci?ed solely in terms of the blocks of consecutive symbols that occur in a word. We'll start by considering lan

In Exercise 9 you showed that the recognition problem and universal recognition problem for SL2 are decidable. We can use the structure of Myhill graphs to show that other problems

Explain Theory of Computation ,Overview of DFA,NFA, CFG, PDA, Turing Machine, Regular Language, Context Free Language, Pumping Lemma, Context Sensitive Language, Chomsky Normal For

proof ogdens lemma .with example i am not able to undestand the meaning of distinguished position .

We developed the idea of FSA by generalizing LTk transition graphs. Not surprisingly, then, every LTk transition graph is also the transition graph of a FSA (in fact a DFA)-the one

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


Paths leading to regions B, C and E are paths which have not yet seen aa. Those leading to region B and E end in a, with those leading to E having seen ba and those leading to B no