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
Computations are deliberate for processing information. Computability theory was discovered in the 1930s, and extended in the 1950s and 1960s. Its basic ideas have become part of

i have some questions in automata, can you please help me in solving in these questions?

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

write short notes on decidable and solvable problem

build a TM that enumerate even set of even length string over a

Given any NFA A, we will construct a regular expression denoting L(A) by means of an expression graph, a generalization of NFA transition graphs in which the edges are labeled with

The universe of strings is a very useful medium for the representation of information as long as there exists a function that provides the interpretation for the information carrie

Explain Theory of Computation ,Overview of DFA,NFA, CFG, PDA, Turing Machine, Regular Language, Context Free Language, Pumping Lemma, Context Sensitive Language, Chomsky Normal For

De?nition (Instantaneous Description) (for both DFAs and NFAs) An instantaneous description of A = (Q,Σ, δ, q 0 , F) , either a DFA or an NFA, is a pair h q ,w i ∈ Q×Σ*, where

The key thing about the Suffx Substitution Closure property is that it does not make any explicit reference to the automaton that recognizes the language. While the argument tha