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
matlab v matlab

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

shell script to print table in given range

Strictly 2-local automata are based on lookup tables that are sets of 2-factors, the pairs of adjacent symbols which are permitted to occur in a word. To generalize, we extend the

constract context free g ={ a^n b^m : m,n >=0 and n

Our primary concern is to obtain a clear characterization of which languages are recognizable by strictly local automata and which aren't. The view of SL2 automata as generators le

De?nition Instantaneous Description of an FSA: An instantaneous description (ID) of a FSA A = (Q,Σ, T, q 0 , F) is a pair (q,w) ∈ Q×Σ* , where q the current state and w is the p


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

implementation of operator precedence grammer