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
i want to do projects for theory of computation subject what topics should be best.

(c) Can you say that B is decidable? (d) If you somehow know that A is decidable, what can you say about B?

Exercise:  Give a construction that converts a strictly 2-local automaton for a language L into one that recognizes the language L r . Justify the correctness of your construction.

The upper string r ∈ Q+ is the sequence of states visited by the automaton as it scans the lower string w ∈ Σ*. We will refer to this string over Q as the run of A on w. The automa

Different types of applications and numerous programming languages have been developed to make easy the task of writing programs. The assortment of programming languages shows, dif

s-> AACD A-> aAb/e C->aC/a D-> aDa/bDb/e

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

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

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

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