Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?

Question

How can I prove that the language that the operator $A$ defines for regular language $L$ is a context free language.

$A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$, where $x^R$ is the reversed form of $x$.

I understand that since $L$ is regular so does $L^R$.also on my way for a CFG I can reach $w_1$ by the CFG of $L$ concatenation with the one of $L^R$ for making $w_2$. so far I have a CFG, but what promises me that $|w_1|=|w_2|$? how can I generate a grammar that will also keep that in addition to the other conditions?

Answer 1

You can show that it is decided by a PDA.

Check if the input string up to $i$th symbol is in $L$ while pushing them to the stack. Then check if the rest of the string is also in $L^R$ while poping one symbol from the stack for each symbol you read. (Note that if $L$ is a regular language so is $L^R$ and memberships in $L$ and $L^R$ can be checked without by DFAs, i.e. no stack is needed for that part.)

You can guess $i$ nondeterministically.

Answer 2

Let $A'(L)= \{ w_1 \sharp w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ where $\sharp$ is a new symbol.

$A'(L)$ is the intersection of context-free language $\{ w_1 \sharp w_2: |w_1|=|w_2|\}$ and regular $L\sharp L^R$, therefore it is context-free. $A(L)$ is a homomorphic image of $A'(L)$, so it is context-free as well.

I prefer this proof to others as it is "higher-level".

Answer 3

You can prove it's context-free by providing a PDA that accepts it (and proving the PDA works, typically by construction).

A PDA could work as follows. Read symbols and count them using the stack. Nondeterministically determine when you've read half the symbols. If what you've seen so far isn't in the regular language, crash or otherwise reject. Otherwise, read the same number of symbols you previously read. If what you read the second time around is in the reverse of the regular language, accept. To formally produce the machine construction, you just need DFAs for the language and its reverse, a way to connect them, and a way to count using a stack.

Answer 4

As $L$ is regular, it is generated by a right-linear grammar for which all rules have the form $A \to aB$, $A \to a$ or $A \to \varepsilon$ (showing this is an easy exercise). So without loss of generality, we assume that $G=(N,T,\delta,S)$ with $\mathcal{L}(G)=L$ has this form.

Now we construct a new grammar that generates $A(L)$. The idea is to "execute" the grammar two times in parallel; because every rule generates at most one terminal, we can achieve the $|w_1|=|w_2|$ requirement. As for $w_2^R \in L$, that should be easy to transfer from the proof that $\mathrm{REG}$ is closed against reversal (if done via grammars).

Formally, we construct $G'=(N',T,\delta', (S,S))$ with
* $N' = N \times N$
* $\delta'$ is defined by
$\quad$ - $(A_1,A_2) \to_{\delta'} a_1(B_1,B_2)a_2 \quad \Longleftrightarrow \quad A_1 \to_\delta a_1B_1 \wedge A_2 \to_\delta a_2B_2$,
$\quad$ - $(A_1,A_2) \to_{\delta'} a_1a_2 \quad \Longleftrightarrow \quad A_1 \to_\delta a_1 \wedge A_2 \to_\delta a_2$,
$\quad$ - $(A_1,A_2) \to_{\delta'} \varepsilon \quad \Longleftrightarrow \quad A_1 \to_\delta \varepsilon \wedge A_2 \to_\delta \varepsilon$

Proof of correctness works via induction over word length resp. number of derivation steps.