Is the language A = {0^n 1^n 0^n} context free?

Question

I was just putting some thought into different languages (as I'm reviewing for final exams coming up) and I can not think of a valid pushdown automata to handle the language A = {0^n 1^n 0^n | n >= 0}. This is not a context-free language, am I correct?

Answer 1

I believe you are. It looks quite similar to the language L = { a^i b^i c^i | i > 0 } which the Wikipedia article on the pumping lemma uses as an example of how to prove that a language is not context-free.

Answer 2

Think of just the {0^n 1^n} part for a second. Replace 0 with ( and 1 with ) and you've got the language of simple nested parentheses, which is a dead give-away that a language is not regular.

Adding the final 0^n makes it context-sensitive (i.e. not context-free). Keep in mind that a CFG can be decided by a finite-state computer with a single stack as its only data structure. Seeing a 0 will cause a character to be pushed onto the stack, and seeing a 1 will pop from the stack. This guarantees that there are as many 0's as 1's, but there's no way to then match more 0's.