1 votes 1 votes Show that the language $L=${$a^nb^nc^m,n\neq m$} is not context-free. Theory of Computation peter-linz peter-linz-edition4 theory-of-computation pumping-lemma context-free-language + – Naveen Kumar 3 asked Jun 25, 2019 Naveen Kumar 3 480 views answer comment Share Follow See 1 comment See all 1 1 comment reply Shubham Shukla 6 commented Jun 25, 2019 reply Follow Share @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. 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes 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. Satbir answered Jun 25, 2019 Satbir comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes The language is not context free as we require two comparisons , for that we require two stacks (turing machine). Sanandan answered Oct 3, 2020 Sanandan comment Share Follow See all 0 reply Please log in or register to add a comment.