context free grammar

Question

Is L2 same as a^i b^j c^j , i,j >=0?

Answer 1

L1 : It is not CFL as we have compared i and j, now we can't compare j again

L2 : It is CFL. (i<=j or j<=i) means we don't have to compare i and j. It is obvious either i>=j or j>=i,  only j and k will be compared. It is not equal to aⁱb^jc^j(i,j>0)

L3 : It is not CFL. After comparing a and b we don't know about n and m for the comparison of c and d.

L4 : It is CFL. First we will compare i, j if it is equal then count for even value of k, if i and j are not equal we don't care about k.

Answer is 2;

Comments

What is L2?

---

L2 is CFL it is like aⁱb^jc^k (j=k).

In this language either i>j or i<j or i=j (we don't care), which is equal to L2.

---

Can L4 be implemented using a DCFL ?

---

How L3 is not CFL?
Push A’s then push B’s pop B on seeing C then pop A on seeing D as number of B’s and C’s are same and no.of A’s and D’s are same.