If $L$ is regular then $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free

Question

I have found a problem about proving whether $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free or not, knowing that $L$ is regular

So far I know that:

• There are examples where $L$ is regular and $L^{|2|}$ is regular (for example $L=\{a,b\}$)
• There are examples where $L$ is regular and $L^{|2|}$ is not (for example $L=\{w \mid w=a^N \text{ or } w= b^N\ , N\ge0\}$)

But I am not sure how to prove that it's context-free regardless of which regular language I use. I have found similar problems with the same language without imposing restrictions on which words to use, but I am not sure if those apply to this one.

Answer 1

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}}_0\rangle$, 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.

Answer 2

Let $\Sigma' = \{\sigma' : \sigma \in \Sigma\}$ be a tagged version of the alphabet of $\Sigma$. Let $L'$ be a version of $L$ obtained by tagging all letters. Let $h\colon \Sigma \cup \Sigma' \to \Sigma$ be a homomorphism which removes tags. Then $$ L^{|2|} = h(LL' \cap \{xy : x \in \Sigma^n, y \in \Sigma^{\prime n} \text{ for some } n\}). $$ Standard closure properties of context-free languages imply that $L^{|2|}$ is context-free.

Answer 3

Let $L$ be a regular language, then $L$ has both a left linear grammar and a right linear grammar.

The right linear grammar $G_R$ has axiom $S_L$ and productions of the form $A\to_R aB$ or $A\to_R\varepsilon$, and the left linear grammar has axiom $S_L$ and productions of the form $P\to_L Qa$ or $P\to_L\varepsilon$. Note that the left linear grammar is deriving its strings 'backwards', so from right to left. (We can directly construct such grammars from a finite automaton for $L$.)

Now we can construct a context-free grammar $G$ (actually a linear grammar) that simulates two derivations in parallel, and by construction they are of the same length. The variables of the CFG $G$ are pairs of variables of $G_R$ and $G_L$. I will write them as $\langle AP\rangle$, buth you might prefer $N_{AP}$.

• axiom $\langle S_RS_L\rangle$
• productions $\langle AP\rangle \to a\,\langle BQ\rangle\, b$, if $A\to_R aB$ and $P\to_L Qb$
• productions $\langle AP\rangle \to \varepsilon$, if $A\to_R \varepsilon$ and $P\to_L \varepsilon$

Answer 4

Here is a sketch of an NPDA for $L^{|2|}$ given a regular language $L$.

If $L$ is regular then it has a DFA $M$. We assume for simplicity that $M$ has one final state only. Create two NPDA from $M$. One is $M_{push}$ which is $M$ but with a stack such that every time it reads an input it pushes a symbol, say $X$. The other NPDA is $M_{pop}$ that pops the stack each time it reads an input. By construction, $M_{pop}$ will not accept any input since initially the stack is empty. However, it will be useful in combination with $M_{push}$ if they work in sequence, which we now take advantage to contruct the NPDA for $L^{|2|}$.

We now construct NPDA $M'$ for $L^{|2|}$. From the final state of $M_{push}$ create a transition that reads no input and does not push nor pop going to the start state of $M_{pop}$. Finally, make the final state of $M_{push}$ an ordinary state.