in Theory of Computation
394 views
1 vote
1 vote
Show that the language $L=${$a^nb^nc^m,n\neq m$} is not context-free.
in Theory of Computation
394 views

1 comment

@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
1

2 Answers

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.
0 votes
0 votes
The language is not context free as we require two comparisons , for that we require two stacks (turing machine).

Related questions