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
Proof (sketch): Suppose L 1 and L 2 are recognizable. Then there are DFAs A 1 = (Q,Σ, T 1 , q 0 , F 1 ) and A 2 = (P,Σ, T 2 , p 0 , F 2 ) such that L 1 = L(A 1 ) and L 2 = L(

So we have that every language that can be constructed from SL languages using Boolean operations and concatenation (that is, every language in LTO) is recognizable but there are r

Normal forms are important because they give us a 'standard' way of rewriting and allow us to compare two apparently different grammars G1  and G2. The two grammars can be shown to

Prepare the consolidated financial statements for the year ended 30 June 2011. On 1 July 2006, Mark Ltd acquired all the share capitall of john Ltd for $700,000. At the date , J

automata of atm machine

Strictly 2-local automata are based on lookup tables that are sets of 2-factors, the pairs of adjacent symbols which are permitted to occur in a word. To generalize, we extend the

A problem is said to be unsolvable if no algorithm can solve it. The problem is said to be undecidable if it is a decision problem and no algorithm can decide it. It should be note

A context free grammar G = (N, Σ, P, S)  is in binary form if for all productions A we have |α| ≤ 2. In addition we say that G is in Chomsky Normaml Form (CNF) if it is in bi

Automaton (NFA) (with ε-transitions) is a 5-tuple: (Q,Σ, δ, q 0 , F i where Q, Σ, q 0 and F are as in a DFA and T ⊆ Q × Q × (Σ ∪ {ε}). We must also modify the de?nitions of th

Find the Regular Grammar for the following Regular Expression:                    a(a+b)*(ab*+ba*)b.