# Working of PDA for $\{a^m b^n c^k \mid m=n \text{ or } n=k\}$

I understand that the language $$L = \{ a^mb^nc^k \mid m=n \text{ or } n=k \}$$ is context-free because it can be represented as the union of $$L_1 = \{a^mb^mc^k\}$$ and $$L_2 = \{a^mb^kc^k\}$$, which are both context-free. But I can't figure out the working of the PDA accepting $$L$$.

To check whether $$m=n$$, first of all $$m$$ many $$a$$'s will be pushed, then on every occurrence of $$b$$, one $$a$$ will be popped out, or if stack becomes empty, then remaining $$b$$'s will be pushed. After this, either stack will be empty, meaning $$m=n$$, or $$m-n$$ many $$a$$'s or $$n-m$$ many $$b$$'s will remain in the stack, meaning $$m \neq n$$. How can we check whether $$n=k$$ now?

## 1 Answer

The PDA first guesses whether $$m=n$$ or $$n=k$$. According to the guess, it either just checks that $$m=n$$, or just checks that $$n=k$$.

What your heuristic argument suggests is that this language cannot be accepted by a deterministic PDA. You can likely show this by adapting the proof here.