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
Automaton (NFA) (with ε-transitions) is a 5-tuple: (Q,Σ, δ, q 0 , F i where Q, Σ, q 0 and F are as in a DFA and T ⊆ Q × Q × (Σ ∪ {ε}). We must also modify the de?nitions of th


distinguish between histogram and historigram

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

matlab v matlab



a) Let n be the pumping lemma constant. Then if L is regular, PL implies that s can be decomposed into xyz, |y| > 0, |xy| ≤n, such that xy i z is in L for all i ≥0. Since the le

We will assume that the string has been augmented by marking the beginning and the end with the symbols ‘?' and ‘?' respectively and that these symbols do not occur in the input al

s-> AACD A-> aAb/e C->aC/a D-> aDa/bDb/e