Sipser Exercise 2.44


Theorem: If and are regular, then is context-free.


Proof: There are finite automatons and that recognize and , respectively. Let the be deterministic, and write and .

So, we construct a PDA for . The machine will work by progressing through ’s machine, pushing a counter on to the stack. Each time it hits one of ’s accepting states, it will make a non-deterministic guess that its passed the mid-point of the string, and spawn a thread transitioning to the starting state of . It will then progress through ’s machine, popping the counters off the stack. If the machine is in a final state of when the stack is empty, it transitions to an accept state (of course, if there is more input, the thread that wound up in the accept state will terminate).

Let , accepting by final state. Let and . Let . Finally, let .

Now, we define as follows.

Where conditions not written result in . This machine accepts , so is context free.