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
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

Design a turing machine to compute x + y (x,y > 0) with x an y in unary, seperated by a # (descrition and genereal idea is needed ... no need for all TM moves)

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

The Equivalence Problem is the question of whether two languages are equal (in the sense of being the same set of strings). An instance is a pair of ?nite speci?cations of regular

Ask question #Minimum 100 words accepte

Suppose A = (Σ, T) is an SL 2 automaton. Sketch an algorithm for recognizing L(A) by, in essence, implementing the automaton. Your algorithm should work with the particular automa

i want to do projects for theory of computation subject what topics should be best.

It is not hard to see that ε-transitions do not add to the accepting power of the model. The underlying idea is that whenever an ID (q, σ  v) directly computes another (p, v) via

The generalization of the interpretation of strictly local automata as generators is similar, in some respects, to the generalization of Myhill graphs. Again, the set of possible s