Sipser 2.44 If A and B are languages, define A ◊ B = {xy | x ∈ A and y ∈ B and |x| = |y|}. Show that if A abd B are regular languages then A ◊ B is a CFL.

Sipser 2.44 If A and B are languages, define A ◊ B = {xy | x ∈ A and y ∈ B and |x| = |y|}. Show that if A abd B are regular languages then A ◊ B is a CFL.

Solution:

Consider M1 and M2 be DFAs for A and B respectively. Now we will construct PDA P for A ◊ B using M1 and M2. On input string z to P, start running it on M1 and go on pushing symbols on stack. When you see that M1 is in final state at some point of time, guess non-deterministically that machine have seen first half i.e. x. And now P have to run remaining. So now start running it on B and go on poping symbols from stack. If input is done and stack is empty at same time and also M2 is in final state then accept, else reject.