Test series

Question

Which of the following is not Context free language?

1.  L={(ab)²ⁿ b^3m│n>0,m>0}
2.  L={aⁿ b^m cⁿ d²ⁿ│n≥0,m>0}
3.  L={aⁿ b^m│0≤n≤m≤2n}
4.   L={aⁿ b²ⁿ c^m│0≤n≤m}

Comments

I think 2nd one.

---

2 and 4.

Answer 1

2nd  and 4th are not CFL

Answer 2

Explanation:
i) L={(ab)²ⁿ b^3m│n,m>0}is a Regular language
⇒It is a Context free language
∵L_1=(ab)²ⁿ is a Regular language
L_2=b^3mis a Regular language
Concatenation of L₁∙L₂ is a Regular language.
(ii) L={aⁿ b^m cⁿ d²ⁿ│n≥0,m>0}
is a Context free language.
∵ S→aSdd|A
A→bAc|bcis the Context free grammar that generates the given language.
(iii) L={aⁿ b^m│0≤n≤m≤2n}
is a Context free language.
∵S→aSb|aSbb|ϵ is the context free grammar that generates the language L.
(iv)L={aⁿ b²ⁿ c^m│0≤n≤m}
is a Context Sensitive language.

Comments

I think the answer you have provided for point 2 is for language  L={an bm cm d2n│n≥0,m>0}
not for L={an bm cn d2n│n≥0,m>0}

---

yes you right plz explain this correctly

 

Answer 3

1. L={(ab)²ⁿ b^3m│n>0,m>0}  is REGULAR & CFL(DFA is possible)
2.  L={aⁿ b^m cⁿ d²ⁿ│n≥0,m>0} is CFL(in PDA push 3a's for 1a)
3.  L={aⁿ b^m│0≤n≤m≤2n} is not CFL
4.   L={aⁿ b²ⁿ c^m│0≤n≤m} is CFL (in PDA push 3a's for 1a)