Myhill graphs, Theory of Computation

Another way of representing a strictly 2-local automaton is with a Myhill graph. These are directed graphs in which the vertices are labeled with symbols from the input alphabet of the automaton (plus {x,x}), with an edge from a vertex labeled σ1 to a vertex labeled σ2 ix the pair σ1σ2 is included in T. (Note that if we interpret the strings in T as pairs of symbols, then the Myhill graph of A = (Σ, T) is just G = (Σ+, T).) The Myhill graph of the automaton of Figure 2 is given in Figure. For consistency with the graphs we will use later, the entry point to the graph is indicated with an edge "from nowhere" and the exit point is indicated by circling it.

The key property of Myhill graphs is that every path through the graph from the ‘x' node to the ‘x' node corresponds to a computation of the automaton and every computation of the automaton corresponds to such a path. So we can reason about the strings that are accepted by the automaton by reasoning about the sequences of nodes that occur on paths from ‘x' to ‘x'. (For simplicity, we will refer to paths from ‘x' to ‘x' as "paths through the graph".)

For example, the shortest strings in the language recognized by the automaton will those labeling the shortest paths through the graph, which is to say, the acyclic paths from ‘x' to ‘x'. In this particular case, these are the paths (x,x) and (x, a, b,x), corresponding to the strings ε and ab.

Posted Date: 3/21/2013 5:54:10 AM | Location : United States







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

Write discussion on Myhill graphs
Your posts are moderated
Related Questions
Another striking aspect of LTk transition graphs is that they are generally extremely ine?cient. All we really care about is whether a path through the graph leads to an accepting

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

We now add an additional degree of non-determinism and allow transitions that can be taken independent of the input-ε-transitions. Here whenever the automaton is in state 1

write short notes on decidable and solvable problem

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

how to understand DFA ?

what exactly is this and how is it implemented and how to prove its correctness, completeness...

The language accepted by a NFA A = (Q,Σ, δ, q 0 , F) is NFAs correspond to a kind of parallelism in the automata. We can think of the same basic model of automaton: an inpu

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 hav

proof ogdens lemma .with example i am not able to undestand the meaning of distinguished position .