6
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Beat me to it. Darned smart phone. $\endgroup$ – Patrick87 Apr 30 '12 at 17:18
  • $\begingroup$ For clarity, mention that membership in $L$ can be checked without the stack, because it's regular. Also, you did not address the reversal issue, though that is easy. $\endgroup$ – David Lewis Apr 30 '12 at 17:47
  • $\begingroup$ @Patrick87, not by much, also I had a typo. :) $\endgroup$ – Kaveh Apr 30 '12 at 18:11
8
$\begingroup$

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".

$\endgroup$
  • 2
    $\begingroup$ I was thinking about something similar. I agree this is a nicer proof. :) $\endgroup$ – Kaveh Apr 30 '12 at 19:06
  • $\begingroup$ Best answer, imho, because it is reduces to the essence and a complete formal proof! $\endgroup$ – Raphael May 9 '12 at 11:46
  • $\begingroup$ And of course also works given two (regular) languages, and requiring $w_1\in L_1$, $w_2\in L_2$. $\endgroup$ – Hendrik Jan Jan 2 '13 at 1:14
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.