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

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?

Answers


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.


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.


Need Your Help

WebSite address from Strings

java android

I don't know why i can't build url from Strings, I want to send some variable with GET method.

Check status of local Python relative to remote with GitPython

python git

How can I use GitPython to determine whether: