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

Yes for linear powers u can verify like this .If however u are given like :

L = {0^{n^2}}  , then it is should not CFL as it cannot be implemented by PDA.Non linear powers are not allowed in CFL.

---

@Habib your explanation with Aand C is correct but i think you have not modelled B language correctly.

---

Ok I got your point..Let me correct..:)

---

@Habib

We know each of these sublanguages are CFL(also DCFL) but the result is not going to DCFL as DCFL is not closed under union

Again you made the same mistake of saying "NO" for not closed. IT should be may or may not DCFL. In this case it is not DCFL.

Also CFL is closed under "finite union" - is it closed under infinite union?

---

@arjun sir, I think no language is closed under infinite union. Am I right?????

---

Ya I agree with u @Arjun sir .. The non violation of closure property does not guarantee the class of language..But as far as this specific language , it contains the element of non determinism as no of push - pops is not clear.

Hence it is not DCFL..

---

@habib It should not be CFL also right?? Bcoz two comparison are required simultaneously that it musr be greater than n and smaller than 3n. Two comparuson cannot be done by using single stack. Right??

---

Not simultaneously..They are combined using "OR" (union) not "AND" (intersection)..

---

@Rahul If this could help

Transitions for L ={ a^m bⁿ , m<=n<=3m} 

M = ({q₀,q₁ q₂ },{a,b},{a,b,B},q₀,q_f )
δ(q₀,a,z)={(q₀,az) },
δ(q₀,a,z)={(q₀,aaz) },
δ(q₀,a,z)={(q₀,aaaz) },
δ(q₀,a,a)={(q₀,aa) },
δ(q₀,a,a)={(q₀,aaa) },
δ(q₀,a,a)={(q₀,aaaa) },
δ(q₀,b,a)={(q₁,ϵ) },
δ(q₁,b,a)={(q₁,ϵ) },
δ(q₁,B,z)={(q_f,z) }.

---

@Habib this is going towards infinite union how is this CFL??? And @Kantikumar in your pda it is true we will not have n exceed 3m but we can have n smaller than m also, then how is this possible to do two comparisons??? 2 should not be CFL correct??

---

@Rahul how is that happening? I hope you have noticed small difference between language given in question and language in my comment.

---

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