# formal languages – If \$L\$ is regular then \$L^{|2|}={w_1w_2 mid w_1,w_2in L, |w_1|=|w_2|}\$ is context-free

Let $$mathcal{A}$$ be a DFA for $$L$$. A direction is to consider a PDA $$mathcal{B}$$ for $$L^{|2|}$$ that is defined on top of the product of $$mathcal{A}$$ with itself, that is, the state-space of $$mathcal{B}$$ is $$(Q_{mathcal{A}} cup { null})times Q_mathcal{A}$$, where $$null$$ is a special state that is not in $$Q_{mathcal{A}}$$, to be explained below. The PDA $$mathcal{B}$$ operates as follows. The initial state of $$mathcal{B}$$ is $$langle q^{mathcal{A}}_0, q^{mathcal{A}}_0rangle$$, that is, both coordinates are initialized to the initial state of $$mathcal{A}$$. The PDA $$mathcal{B}$$ modifies only the left coordinate or the right coordinate at a time. $$mathcal{B}$$ starts by simulating the run of $$mathcal{A}$$ on the left coordinate while pushing input letters into the stack. When $$mathcal{B}$$ reaches an accepting state in the left coordinate, it guesses to do one of the following:

1- it guesses that it just finished reading the prefix $$w_1$$, so it modifies the left coordinate to $$null$$, and operates from this point on only on the right coordinate that takes care of the suffix $$w_2$$.

2- it guesses that we did not finish reading the prefix $$w_1$$, and continues to modify the left coordinate.

If at some point $$mathcal{B}$$ guess option 1 above, then $$mathcal{B}$$ runs $$mathcal{A}$$ on the right coordinate, and at the same time checks whether $$|w_1| = |w_2|$$ which can be done by popping letters from the stack for each input letter that we read. For example, if at some point the stack becomes empty, and we did not finish reading the input, this means that in the current guess $$|w_2| > |w_1|$$, and thus we move to a rejecting sink. $$mathcal{B}$$ only accepts if the stack is empty and the 2nd coordinate is an accepting state of $$mathcal{A}$$. To define $$mathcal{B}$$ formally, you might need an additional binary coordinate (or you can use the left coordinate) to indicate whether the stack just became empty. Then, the accepting states of $$mathcal{B}$$ are those having $$null$$ in the left coordinate, an accepting state in the right coordinate, and the additional coordinate specifies that the stack just became empty.

I only gave the general idea, I leave the details to you.

Edit: note that you can easily modify the above construction so that the number of states of $$mathcal{B}$$ is linear in $$|Q_{mathcal{A}}|$$. To see why, note that both the first and the second simulation can be done on the same coordinate, you only need a bit to remember which simulation we’re doing now.

Posted on