Context Free Language

Question

Which of the following is not context free?

$I) L_{1}=\left \{ a^{i}b^{j}c^{k} |i,j,k\geq 0,i<j<k \right \}$

$I) L_{2}=\left \{ a^{i}b^{j}c^{k} |i,j,k\geq 0, j=max\left ( i,k \right )\right \}$

Comments

#Bhawna how will you check i>k if j counts in between.. I mean we can ignore counting of b but that would be again a problem to check whether j=i or not..

---

but there are two comparisons 1. i and k

                                                  2.j and k or j and i

---

@vaibhav yes you are correct. It will be difficult by that method to reject the strings not in the grammar as once we lose track of #$a's$ and if we encounter #$a's$ $\neq$ #$b's$ then we cannot backtrack to compare #$a's$ and #$c's$