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
Let there L1 and L2 . We show that L1 ∩ L2 is CFG . Let M1 be a decider for L1 and M2 be a decider for L2 . Consider a 2-tape TM M: "On input x: 1. copy x on the second

Kleene called this the Synthesis theorem because his (and your) proof gives an effective procedure for synthesizing an automaton that recognizes the language denoted by any given r

A Turing machine is a theoretical computing machine made-up by Alan Turing (1937) to serve as an idealized model for mathematical calculation. A Turing machine having of a line of

Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

let G=(V,T,S,P) where V={a,b,A,B,S}, T={a,b},S the start symbol and P={S->Aba, A->BB, B->ab,AB->b} 1.show the derivation sentence for the string ababba 2. find a sentential form

Construct a PDA that accepts { x#y | x, y in {a, b}* such that x ? y and xi = yi for some i, 1 = i = min(|x|, |y|) }. For your PDA to work correctly it will need to be non-determin

We now add an additional degree of non-determinism and allow transitions that can be taken independent of the input-ε-transitions. Here whenever the automaton is in state 1

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

Can v find the given number is palindrome or not using turing machine

Let G be a graph with n > 2 vertices with (n2 - 3n + 4)/2 edges. Prove that G is connected.