IIT Kanpur

Question

6. let E ={a,b,c}. Which of the following sets are context-free languages
    A. X = {aⁱ b^j c^k | i < j < k}
    B. Y = (the complement of X)
    C. Z = {aⁿ b²ⁿ c^3m | n, m >=0}
    D. None of the above sets are context free languages.

Comments

Thanks

---

Soumya how B is CFL. Becuase in B you always have to check that whether $i \lt j \lt k$ condition becomes true or not.

---

See What I did -
X = {aⁱ b^j c^k | i < j < k} 
Break it in 2 parts- {aⁱ b^j | i<j } $\cap$ {b^j c^k | j<k }  // It in not CFL
X' = Y = ({ai bj | i<j } $\cap$ {bj ck | j<k })'  = {ai bj | i>j } $\cup$  {bj ck | j>k }

Let,
L1 = {ai bj | i>j }  \\ CFL
L2 = {bj ck | j>k } \\ CFL
Y = L1 $\cup$ L2
Union of 2 CFLs is CFL

Answer 1

Ans is B, C

X = {aⁱ b^j c^k | i<j<k} for this language simultaneously 2 comparisons required to accept the language.
so using single stack it's not possible. So this is not CFL.

Y = (the complement of X) .The language it represents is
{a i bj ck | i>j} U {ai bj ck | j>k} U {ai bj ck | i>k} U a*c*b* U b*a*c* U b*c*a* U c*a*b* U c*b*a*.
So this language can be recognized by PDA.

C. Z = {aⁿ b²ⁿ c^3m | n,m>=0} .Here only one comparison required for comparing n(a) and n(b).So  can  be recognized by PDA.

Comments

$ a^ib^jc^k / i\lt j \geq k$ is not in ur language.