4
$\begingroup$

I am learning about context free languages.

I understand how $\{a^n b^n c^n | n \ge 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^n b^n c^n | n \ge 0\}$ can be constructed. This PDA would initially push two $a$'s into its stack whenever it sees an $a$ in the input. It would change state when it first encounters a $b$ and pop a single $a$. It would continue to pop $a$'s for every b in the input until it encounters a $c$. 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^n b^n c^n | n \ge 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.

$\endgroup$
14
$\begingroup$

Your PDA would also accept strings of the form $a^nb^ic^j$ where $i+j=2n$ and $i,j>0$. For example the string "aaabbbbbc" is accepted. There is no way to tell that there are exactly $n$ $a$'s still remaining on the stack once you've finished reading the $b$'s.

$\endgroup$
0
$\begingroup$

The PDA would accept the strings which are not present in the languages . For example a string 'aabccc' can also be accepted by the PDA by popping out each a when it encounter b by changing the state anf when it encounters 'c' it will again pop out 'a' . Therefore PDA for a^nb^nc^n is not possible .

$\endgroup$
  • $\begingroup$ Could you elaborate your answer? So you pop "a" all the time? How does it prove that such PDA cannot exist? $\endgroup$ – Evil Nov 22 '16 at 14:44
-1
$\begingroup$

You are trying to say that for every a read from the tape you will push two a's on the stack then string aabccc will also be accepted by this PDA which is not part of given language

$\endgroup$
  • 3
    $\begingroup$ This exact example was posted nearly two years ago. It really is great that you're trying to help out but please only answer if you have something new to say. Duplicating existing answers just clutters up the page and makes things harder to find. $\endgroup$ – David Richerby Sep 8 '18 at 16:09

protected by Community Sep 8 '18 at 17:10

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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