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
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 Myhill-Nerode Theorem provided us with an algorithm for minimizing DFAs. Moreover, the DFA the algorithm produces is unique up to isomorphism: every minimal DFA that recognizes

In Exercise 9 you showed that the recognition problem and universal recognition problem for SL2 are decidable. We can use the structure of Myhill graphs to show that other problems

The Last Stop Boutique is having a five-day sale. Each day, starting on Monday, the price will drop 10% of the previous day’s price. For example, if the original price of a product

Give the Myhill graph of your automaton. (You may use a single node to represent the entire set of symbols of the English alphabet, another to represent the entire set of decima

Theorem The class of recognizable languages is closed under Boolean operations. The construction of the proof of Lemma 3 gives us a DFA that keeps track of whether or not a give

Construct a Mealy machine that can output EVEN or ODD According to the total no. of 1''s encountered is even or odd.

prove following function is turing computable? f(m)={m-2,if m>2, {1,if

how to prove he extended transition function is derived from part 2 and 3

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