Myhill-nerode, Theory of Computation

Theorem (Myhill-Nerode) A language L ⊆ Σ is recognizable iff ≡L partitions Σ* into ?nitely many Nerode equivalence classes.

Proof: For the "only if" direction (that every recognizable language has ?nitely many Nerode equivalence classes) observe that L ∈ Recog iff L = L(A) for some DFA A and that if δ(q0,w) = δ(q0, u) (i.e., if the path from the start state labeled w and that labeled u end up at the same state) then w ≡L u. This is a consequence of the fact that the state ˆ δ(q0,w) encodes all the information the automaton remembers about the string w. If v extends w to wv ∈ L(A) then v is the label of a path to an accepting state from δ(q0,w). Since this is the same state as δ(q0, u) the same path witnesses that uv ∈ L. Similarly, if the path leads one to a non-accepting state then it must necessarily lead the other to the same state. The automaton has no way of distinguishing two strings that lead to the same state and, consequently, the language it recognizes cannot distinguish them. Since A is deterministic, every string in Σ* labels a path leading to some state, hence the equivalence classes corresponding to the states partition Σ*. Since the automaton has ?nitely many states, it distinguishes ?nitely many equivalence classes.

Posted Date: 3/25/2013 1:20:59 AM | Location : United States

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

Write discussion on Myhill-nerode
Your posts are moderated
Related Questions
how to find whether the language is cfl or not?

Differentiate between DFA and NFA. Convert the following Regular Expression into DFA. (0+1)*(01*+10*)*(0+1)*. Also write a regular grammar for this DFA.

Paths leading to regions B, C and E are paths which have not yet seen aa. Those leading to region B and E end in a, with those leading to E having seen ba and those leading to B no

1. Simulate a TM with infinite tape on both ends using a two-track TM with finite storage 2. Prove the following language is non-Turing recognizable using the diagnolization

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

construct a social network from the real-world data, perform some simple network analyses using Gephi, and interpret the results.

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 many pendulum swings will it take to walk across the classroom?

One might assume that non-closure under concatenation would imply non closure under both Kleene- and positive closure, since the concatenation of a language with itself is included