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
When we say "solved algorithmically" we are not asking about a speci?c programming language, in fact one of the theorems in computability is that essentially all reasonable program

how to prove he extended transition function is derived from part 2 and 3

Let ? ={0,1} design a Turing machine that accepts L={0^m 1^m 2^m } show using Id that a string from the language is accepted & if not rejected .

Ask question #hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhMinimum 100 words accepted#

Another way of representing a strictly 2-local automaton is with a Myhill graph. These are directed graphs in which the vertices are labeled with symbols from the input alphabet of

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

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

If the first three words are the boys down,what are the last three words??

The Last Stop Boutique is having a five-day sale. Each day, starting on Monday, the price will drop 10% of the previous day’s price. For example, if the original price of a product

how to convert a grammar into GNF