Is the given language: (regular|context-free|etc)

Assume E = {a, b}. Let L0 = {(b^(n))(a^(2n)) : n >= 0}. Let L = ((NOT OPERATION)L0)

Is L regular, context-free but not regular, or not c开发者_如何学Context-free? Prove your answer.

I'm looking for what L would be, and how to describe it in a similar fashion of how L0 was described in the question, along with the answer.

The explanation is very important to me, if you'd like to contribute, please be specific. I'm looking to understand this material for a test.

Thanks very much!

I will try to explain you using layman's language and hints for you to do formalize it.

L is a language with all the strings of alphabet E={a,b}which are not in language L0 This is a not a regular language.

Strings in L are all the strings which end at non-final states of DFA of L0. But as you can't build DFA/NFA for L0, you can't have a DFA for L too.

Reason: In L0 one unbound number n, which need to be stored after look at all b's then use it while checking a's, DFA have no memory. You can't write a regular expression for above language.

Using Pumpping lemma L is not a Context Free Language

S=ab is a string in L Using PL I'll divide in into 5 parts

S=uvxyz

u="" v=a x="" y=b z=""

Now for n=0 new String is S(n=0)="" which is not in L.

if we divide ab into

   u="" v="" x=a y=b z=""

Now for n=2 S(n=2)=abb which is not in L

So L is not CFG.

PS: Let me know if you find any hole in m

I'm not sure if you've learned the pumping lema. But its a way to tell whether the language is regular. And remember that if L0 is regular then L1 is regular too since you can make a dfa of L1 by swapping the final and initial stats of the L0 dfa.

Consinder any example of L0 where b^m a^2m and this string is big enough for pumping lema.

Divide the example into three parts xyz.

where |xy| < m (number of elements in the substring xy) and |y| >= 1.

Since the chunk xy < m it must be all b's since there are b^m b's.

now lets pump y 0 times.

x y^0 z has so if your lang was bbbaaaaaa and |y|=1 ur lang becomes bbaaaaaa meaning that now it follow b^n a^3n. Which makes it not a regex.

Meaning that L1 is not a regex 2.