0
$\begingroup$

I am learning about context free languages.

I understand how $\{a^nb^nc^n|n>0\}$ can be shown to be not context free using the pumping lemma for CFL's.

Intuitively however it seems that a pushdown automata to recognize $\{a^nb^nc^n|n>0\}$ can be constructed. This PDA would initially push single a's into its stack whenever it sees an a in the input. It would change state when it first encounters a b and do nothing on the stack for every b it encounters. When the first c is encountered, it would again change state and pop single a's for every c encountered. If the stack is empty at the end of the input the language is recognized as $\{a^nb^nc^n|n>0\}$.

There must be something I am overlooking whilst constructing the PDA as a language is context free if its has a PDA recognizing it. Please point out my mistake.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ You are required to match the number of $a$, $b$, and $c$. If you simply ignore the $b$'s then you cannot guarantee that all type of symbols have the same length. $\endgroup$
    – Russel
    Oct 31, 2022 at 13:00

1 Answer 1

Reset to default
3
$\begingroup$

Because there is no control on the number of $b$'s, such a pushdown automaton would recognize $\{a^nb^mc^n\mid n, m> 0\}$ which is indeed context-free.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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