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
Given any NFA A, we will construct a regular expression denoting L(A) by means of an expression graph, a generalization of NFA transition graphs in which the edges are labeled with

Another striking aspect of LTk transition graphs is that they are generally extremely ine?cient. All we really care about is whether a path through the graph leads to an accepting

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

Construct a Mealy machine that can output EVEN or ODD According to the total no. of 1''s encountered is even or odd.

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

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

Application of the general suffix substitution closure theorem is slightly more complicated than application of the specific k-local versions. In the specific versions, all we had

The Myhill-Nerode Theorem provided us with an algorithm for minimizing DFAs. Moreover, the DFA the algorithm produces is unique up to isomorphism: every minimal DFA that recognizes


Question 2 (10 pt): In this question we look at an extension to DFAs. A composable-reset DFA (CR-DFA) is a five-tuple, (Q,S,d,q0,F) where: – Q is the set of states, – S is the alph