Doubts

Question

1.  $a^{2n}b^n$
2. $a^nb^m, m\leq n\leq 3m$
3. $a^nb^m , n=4m$

Which of the following is CFL ?

Answer 1

All  the given languages are CFLs.Let us understand how..

A) a²ⁿ . bⁿ

For this we push the a's till b's do not come in the input.As soon as b starts coming , for every b that is read , pop 2 a's from the stack.Thus the given language can be modelled on deterministic PDA since how many push or pop needs to be done at each step.

Hence it is a DCFL to be more accurate and hence CFL as well

C)a^{4m .}  b^m

For this we proceed in similar manner as in A) .Just the modification that is required is when b starts coming in input for very b that is read , pop 4 a's from the stack.Thus 

Thus the given language can be modelled on deterministic PDA as well since how many push or pop needs to be done at each step.

Hence it is a DCFL to be more accurate and hence CFL as well.

Now coming to B)

B) aⁿ . b^m    such that m <= n <= 3m

Let this language be L.Now L can be decomposed into sublanguages L₀ , L₂ , ......, L_2m as shown below :

L₀  =  { a^m b^m} for m = n

L₁  =  { a^m+1 b^m } for n = m+1

...

...

L_2m = { a^3m b^m} for n = 3m

We know each of these sublanguages are CFL(also DCFL) but the result is not going to DCFL as in the above language the number of pops of 'a' w.r.t 'b'   will vary according to each of the sublanguages.This is not deterministic behaviour and hence cannot be modelled on deterministic push down automata.So it is not DCFL

But yes it can be modelled using non deterministic PDA.

Hence the given language is  CFL but not DCFL

Comments

Got confused, tgought both are same. And both are CSL for me.

---

@Habib I don't think L2 is CFL. In your answer it is infinite union. Can you PLEASE provide a PDA for it? Thank you.

---

It is a CFL . The corresponding CFG is :

S -->  aSb | aaSb | aaaSb  [ The terminating productions are dependent on initial values of m,n ]

Answer 2

Case I

Push all the a' into the stack after crossing all the 'a' whenever u find 'b' ,then correspondingly pop two 'bb' from the top of the stack.

Therefore above languages is CFL so it must be DCFL.

Case 2:"

Second language is nothing but union of two context free say L1={a^n b^n/n>=1}  and L2={a^n b^2n/n>=1} therfore second languages must be CFL not DCFL.

Case 3::

It is obvious that it can be accepted by PDA for every one 'a' pop 4'b'------------->DCFL

Comments

What about "aaabb" ? Is not this in $L_2$?