Awesome q2a theme

0 votes

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?

+1 vote

Best answer

The given language is a non-deterministic Context free language, so we can make a N-PDA(Non-Deterministic PDA) for the given language.(A deterministic push down automata will not be possible).

I tried to make one, hope it helps.

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}$

As transition towards 1 or 3 is not deterministic therefore it is a non-deterministic PDA.

9,105 questions

3,156 answers

14,594 comments

95,955 users