Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
    
Actually it wouldn't accept any other strings than the ones you described. –  Khaur Jan 17 '13 at 16:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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