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
constract context free g ={ a^n b^m : m,n >=0 and n

examples of decidable problems

So we have that every language that can be constructed from SL languages using Boolean operations and concatenation (that is, every language in LTO) is recognizable but there are r

Since the signi?cance of the states represented by the nodes of these transition graphs is arbitrary, we will allow ourselves to use any ?nite set (such as {A,B,C,D,E, F,G,H} or ev

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

The computation of an SL 2 automaton A = ( Σ, T) on a string w is the maximal sequence of IDs in which each sequential pair of IDs is related by |- A and which starts with the in

s->0A0|1B1|BB A->C B->S|A C->S|null find useless symbol?

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

A finite, nonempty ordered set will be called an alphabet if its elements are symbols, or characters. A finite sequence of symbols from a given alphabet will be called a string ove

how to convert a grammar into GNF