gotchaMinor
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$?
Viewed 0 times
whyw_1w_2freeregularlanguagew_2generatecontextdoesfor
Problem
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?
$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?
Solution
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".
$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".
Context
StackExchange Computer Science Q#1592, answer score: 8
Revisions (0)
No revisions yet.