Local myhill graphs, Theory of Computation

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 have just scanned σ1σ2 ....... σk-1 the next symbol is permitted to be σk. The question of whether a given symbol causes the computation to reject or not depends on the preceding k - 1 symbols. Thus, we will take the vertices of the graph to be labeled with strings of length less than or equal to k - 1 over Σ plus one vertex labeled ‘x' and one labeled ‘x'.

We can interpret a k-factor σ1σ2 σk-1σk, then, as denoting an edge between the node labeled σ1σ2 ........σk-1 and that labeled σ2.......σk (the last k - 1 symbols of the string obtained by adding σk to the end of σ1σ2 ........σk-1). While the symbol responsible for the transition along an edge can be determined by looking at the last symbol of the label of the node the edge leads to, for clarity we will label the edges with that symbol as well.

Each of the factors of form xσ2 ........ σk will be interpreted as a path from the vertex labeled x through the vertices labeled with successive pre?xes of σ2 ........ σk, to the vertex labeled σ2 ........ σk with the edges labeled σ2, . . . , σk in sequence. Those of the form σ1 ...... σk-1x will be interpreted as an edge from the vertex labeled σ1 ...... σk-1 to that labeled ‘x', with the edge labeled ‘ε'.

Finally, those of the form xσ1.......σix, for 0 ≤ i < k - 1, (where the substring σ1 ........ σi may be empty) will be interpreted as a path through vertices labeled with successive pre?xes of σ    σ (possibly no intermediate vertices) from the vertex labeled ‘x' to that labeled ‘x', with the edges labeled with σ1, . . . , σi (possibly ε) in sequence.

Posted Date: 3/22/2013 1:27:57 AM | Location : United States







Related Discussions:- Local myhill graphs, Assignment Help, Ask Question on Local myhill graphs, Get Answer, Expert's Help, Local myhill graphs Discussions

Write discussion on Local myhill graphs
Your posts are moderated
Related Questions

We got the class LT by taking the class SL and closing it under Boolean operations. We have observed that LT ⊆ Recog, so certainly any Boolean combination of LT languages will also

i have some questions in automata, can you please help me in solving in these questions?


Suppose A = (Σ, T) is an SL 2 automaton. Sketch an algorithm for recognizing L(A) by, in essence, implementing the automaton. Your algorithm should work with the particular automa

Lemma 1 A string w ∈ Σ* is accepted by an LTk automaton iff w is the concatenation of the symbols labeling the edges of a path through the LTk transition graph of A from h?, ∅i to

State and Prove the Arden's theorem for Regular Expression

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

1. An integer is said to be a “continuous factored” if it can be expresses as a product of two or more continuous integers greater than 1. Example of continuous factored integers

When an FSA is deterministic the set of triples encoding its edges represents a relation that is functional in its ?rst and third components: for every q and σ there is exactly one