Sipser Exercise 2.22


Theorem: The language is context free.


Proof: Note that if and only if is of the form and one of the following is true: (1) , (2) , or (3) and there is some such that .

Let the stack alphabet be with bottom stack symbol , and let represent an arbitrary member of . We design a PDA as follows:

First, the machine progresses through the substring , pushing a onto the stack each time it reads a character. Note that, after reading characters, the machine is in or if the ‘th character was or respectively, and has instances of on the stack.

The bottom path (for ‘unequal’, ‘equal’, and ‘unequal’, respectively) handles length comparison. After the is read, it immediately accepts until the stack is emptied, at which point the strings are equal length, at which case the machine is in . Here, we do not accept on length comparison, and instead rely on the machine to be in to accept (explained below). If any more input is received, the machine goes to and is permanently accepting again. In addition, if a is read as the first character, the two strings are equal length because they are both empty, so the start state transitions to .

The other path handles comparison on equal-length strings. Every time a character is read, the machine ‘spawns a thread’ that immediately progresses to or . The ‘spawned thread’ has knowledge of what the ‘th character of was, along with instances of on the stack. This thread then ignores the rest of , and waits for a symbol. Finally, each version of the machine that makes it to or progresses to the ‘th character of (by popping the instances of off the stack) and tests if the ‘th character of is different than what it knew was the ‘th character of . If this test ever passes, a version of the machine enters and stays there forever, ensuring that the string is accepted.

This machine accepts , so is context-free.