Complement - operations on languages, Theory of Computation

The fact that SL2 is closed under intersection but not under union implies that it is not closed under complement since, by DeMorgan's Theorem

L1 ∩ L2 = 412_lema.png

We know that the intersection of SL2 languages is also SL2. If the complement of SL2 languages was also necessarily SL2, then 412_lema.png would be SL2 contradicting the fact that there are SL2 languages whose union are not SL2.

Lemma The class of strictly 2-local languages is not closed under complement .

Posted Date: 3/22/2013 12:58:56 AM | Location : United States







Related Discussions:- Complement - operations on languages, Assignment Help, Ask Question on Complement - operations on languages, Get Answer, Expert's Help, Complement - operations on languages Discussions

Write discussion on Complement - operations on languages
Your posts are moderated
Related Questions
Suppose G = (N, Σ, P, S) is a reduced grammar (we can certainly reduce G if we haven't already). Our algorithm is as follows: 1. Define maxrhs(G) to be the maximum length of the

We can then specify any language in the class of languages by specifying a particular automaton in the class of automata. We do that by specifying values for the parameters of the

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

What is the purpose of GDTR?

how to convert a grammar into GNF

The path function δ : Q × Σ*→ P(Q) is the extension of δ to strings: Again, this just says that to ?nd the set of states reachable by a path labeled w from a state q in an

Intuitively, closure of SL 2 under intersection is reasonably easy to see, particularly if one considers the Myhill graphs of the automata. Any path through both graphs will be a

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

We got the class LT by taking the class SL and closing it under Boolean operations. We have observed that LT ⊆ Recog, so certainly any Boolean combination of LT languages will also

how to understand DFA ?