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
Let ? ={0,1} design a Turing machine that accepts L={0^m 1^m 2^m } show using Id that a string from the language is accepted & if not rejected .

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

We have now de?ned classes of k-local languages for all k ≥ 2. Together, these classes form the Strictly Local Languages in general. De?nition (Strictly Local Languages) A langu

All that distinguishes the de?nition of the class of Regular languages from that of the class of Star-Free languages is that the former is closed under Kleene closure while the lat

Rubber shortnote

The k-local Myhill graphs provide an easy means to generalize the suffix substitution closure property for the strictly k-local languages. Lemma (k-Local Suffix Substitution Clo

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

De?nition Deterministic Finite State Automaton: For any state set Q and alphabet Σ, both ?nite, a ?nite state automaton (FSA) over Q and Σ is a ?ve-tuple (Q,Σ, T, q 0 , F), w


The Universality Problem is the dual of the emptiness problem: is L(A) = Σ∗? It can be solved by minor variations of any one of the algorithms for Emptiness or (with a little le