36 views
I understand that the language L = {a^m b^n c^k|(m=n)or(n=k)} is CFL because it can be represented as the union of L1 = {a^m b^m c^k} and L2 = {a^m b^k c^k} which are both CFL's. But I can't figure out the working of the PDA accepting L. To check (m=n), first of all m a's will be pushed then on every occurance of b, one a will be popped out. If stack becomes empty then b's will be pushed. After this either stack will be empty meaning (m=n) or (m-n) a's or (n-m) b's will remain in the stack meaning (m!=n). How can we check for (n=k) now?

edited | 36 views

+1 vote
If we transition to state 1 it will accept the strings of type $a^{n}b^{n}c^{m}$
It we transition to state 3 it will accept the strings of type $a^{m}b^{n}c^{n}$