Peter Linz Edition 4 Exercise 8.1 Question 1 (Page No. 212)

Question

Show that the language $L=${$a^nb^nc^m,n\neq m$} is not context-free.

Comments

@Naveen Kumar 3 you need two stacks in here to do 2 comparison first you need to check for equivalence of a and b and second you need to do comaprsion for n≠m, which a normal PDA with single stack cant do,so whenever its more than one comparison than that language is not going to be a context free language.

Answer 1

The language is not context free because we need to do $2$ types of comparisons.

One for checking whether $a^n$=$b^n$ and second for checking whether $n \neq m$ satisfies or not.

Answer 2

The language is not context free as we require two comparisons , for that we require two stacks (turing machine).