Is A = {0 ^ n 1 ^ n 0 ^ n} free?

Question

I was just thinking about different languages ​​(as I consider for the final exams), and I can’t think of valid pushdown machines for processing the language A = {0 ^ n 1 ^ n 0 ^ n | n> = 0}. This is not a context-free language, am I right?

Answer 1

I believe that you are. It looks very similar to the language L = {a ^ i b ^ i c ^ i | i> 0}, which in the Wikipedia article on the pumping lemma is used as an example of how to prove that the language is not contextual.

Answer 2

Remember only the part {0 ^ n 1 ^ n} for a second. Replace 0 with ( and 1 with ) , and you have a language of simple nested parentheses, which is a dead kick, that the language is not regular.

Adding the final 0 ^ n makes it context-sensitive (i.e. not contextual). Keep in mind that CFG can be solved using an end-state computer with a single stack as the only data structure. If you see 0, this will cause the character to be pushed onto the stack and see how 1 appears from the stack. This ensures that the number 0 is 1, but there is no way to match more than 0.