Myhill-nerode theorem, Theory of Computation

This close relationship between the SL2 languages and the recognizable languages lets us use some of what we know about SL2 to discover properties of the recognizable languages. Because they are SL2 languages, the runs of an automaton A (and, equivalently, the strings of pairs licensed by G2A) will satisfy the 2-suffix substitution closure property. This means that every recognizable language L is a homomorphic image of some language L′ (over an alphabet Σ′ , say) for which

                                                             u′1σ′v′1 ∈ L′ and u′2 σ′v′2 ∈ L′⇒ u′1σ′v′2( and u′2σ′v′1) ∈ L′.

Moreover, u′1σ′v′1 ∈ L′ and u′1σ′v′2 ∈ L′⇒ u′2σ′v′2 ∈ L′

The hypothetical u′1σ′ and u′2σ′ are indistinguishable by the language. Any continuation that extends one to a string in L′ will also extend the other to a string in L′ ; any continuation that extends one to a string not in L′ will extend the other to a string not in L′.

For the SL2 language L′ the strings that are indistinguishable in this way are marked by their ?nal symbol. Things are not as clear for the recognizable language L because the homomorphism may map many symbols of Σ′ to the same symbol of Σ. So it will not generally be the case that we can easily identify the sets of strings that are indistinguishable in this way. But they will, nevertheless, exist. There will be pairs of strings u1 and u2 - namely the homomorphic images of the pairs u′1σ′ and u′2σ′-for which any continuation v, it will be the case that u1v ∈ L iff u2v ∈ L.

This equivalence between strings (in the sense of being indistinguishable by the language in this way) is the key to characterizing the recognizable languages purely in terms of the strings they contain in a way analogous to the way suffix substitution closure characterizes the SL2.

Posted Date: 3/25/2013 1:18:54 AM | Location : United States







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

Write discussion on Myhill-nerode theorem
Your posts are moderated
Related Questions
How useful is production function in production planning?

Computer has a single LIFO stack containing ?xed precision unsigned integers (so each integer is subject to over?ow problems) but which has unbounded depth (so the stack itself nev

To see this, note that if there are any cycles in the Myhill graph of A then L(A) will be infinite, since any such cycle can be repeated arbitrarily many times. Conversely, if the

This close relationship between the SL2 languages and the recognizable languages lets us use some of what we know about SL 2 to discover properties of the recognizable languages.

Exercise Show, using Suffix Substitution Closure, that L 3 . L 3 ∈ SL 2 . Explain how it can be the case that L 3 . L 3 ∈ SL 2 , while L 3 . L 3 ⊆ L + 3 and L + 3 ∈ SL

Rubber shortnote

1. An integer is said to be a “continuous factored” if it can be expresses as a product of two or more continuous integers greater than 1. Example of continuous factored integers


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

conversion from nfa to dfa 0 | 1 ___________________ p |{q,s}|{q} *q|{r} |{q,r} r |(s) |{p} *s|null |{p}