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
A finite, nonempty ordered set will be called an alphabet if its elements are symbols, or characters. A finite sequence of symbols from a given alphabet will be called a string ove

First model: Computer has a ?xed number of bits of storage. You will model this by limiting your program to a single ?xed-precision unsigned integer variable, e.g., a single one-by

Applying the pumping lemma is not fundamentally di?erent than applying (general) su?x substitution closure or the non-counting property. The pumping lemma is a little more complica

Different types of applications and numerous programming languages have been developed to make easy the task of writing programs. The assortment of programming languages shows, dif


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

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 inexh

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

The computation of an SL 2 automaton A = ( Σ, T) on a string w is the maximal sequence of IDs in which each sequential pair of IDs is related by |- A and which starts with the in

1. Does above all''s properties can be used to prove a language regular? 2..which of the properties can be used to prove a language regular and which of these not? 3..Identify one