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
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


Myhill graphs also generalize to the SLk case. The k-factors, however, cannot simply denote edges. Rather the string σ 1 σ 2 ....... σ k-1 σ k asserts, in essence, that if we hav

A finite, nonempty ordered set will be called an alphabet if its elements are symbols, or characters. A finite sequence of symbols from a given alphabet will be called a string ove

What are the benefits of using work breakdown structure, Project Management

automata of atm machine

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

i want to do projects for theory of computation subject what topics should be best.


Design a turing machine to compute x + y (x,y > 0) with x an y in unary, seperated by a # (descrition and genereal idea is needed ... no need for all TM moves)