Use the equivalence of contextfree grammars and pushdown aut

Use the equivalence of context-free grammars and pushdown automata to show that if A and B are regular languages, then {xy x element A, y element B, |x| = |y|} is context-free.

Solution

We create a DFA for A and B. Now let us start by constructing the PDA. We join the final state from DFA-A to start from DFA-B. The final state from DFA-A is no longer the final state. The final state from DFA-B is the new final state. Now for all the state in PDA which are originially from DFA-A we push \'1\' on to the stack whenever we visit a state from DFA-A and we pop \'1\' from the stack whenever we visit a node from DFA-B. After reaching the final state if the stack is empty then the string is accepted by the PDA.

As now we have successfully constructed the PDA. So the language is CFG.