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

Define the following concept with an example: a.    Ambiguity in CFG b.    Push-Down Automata c.    Turing Machine

1. Does above all''s properties can be used to prove a language regular? 2..which of the properties can be used to prove a language regular and which of these not? 3..Identify one

And what this money. Invovle who it involves and the fact of,how we got itself identified candidate and not withstanding time date location. That shouts me media And answers who''v

LTO was the closure of LT under concatenation and Boolean operations which turned out to be identical to SF, the closure of the ?nite languages under union, concatenation and compl

write grammer to produce all mathematical expressions in c.

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

can you plz help with some project ideas relatede to DFA or NFA or anything

#Your company has 25 licenses for a computer program, but you discover that it has been copied onto 80 computers. You informed your supervisor, but he/she is not willing to take an

In general non-determinism, by introducing a degree of parallelism, may increase the accepting power of a model of computation. But if we subject NFAs to the same sort of analysis