Hi, 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?
+4
A:
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.
SamB
2010-04-11 19:46:52
To the original poster, I would suggest attempting to follow through the same steps of the proof referred to above with the language you're interested in.
Dale Hagglund
2010-04-11 21:14:24
A:
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 my 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.
baddox
2010-04-14 03:19:10