1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.