# Designing CFG for sequences of words of which two arbitrary ones are reversals

Let $L$ = {$x_1\#x_2\#...\#x_k$ : $k\;\ge\;1$, each $x_i\;\in\;\{0,1\}^*$ and $\exists i,j$ such that $i < j$ and $x_i$ = $x^R_J$}. For example, $001001\#0010\#100100\#00001$ is in $L$ because $001001$ = $100100^R$. Give a context-free grammar for $L$.

So far I have come up with a rule that can generate the string that contains the hash symbol.

$A \rightarrow$ $0A1\;|\;0A0\;|\;1A\;|\;0A\;|\;\#A\;|\;1A1\;|\;A0\;|\;A1\;|\;\epsilon$

How can I design a rule that generates the reverse sequence ? Also I wanna make sure that my rule is correct.

• A good start would be to figure out how to generate the language $\{x\#x^R : x \in \{0,1\}^*\}$. – Yuval Filmus Nov 28 '14 at 6:01
• @YuvalFilmus I think I got it. Is the following grammar correct ? $A \rightarrow\; 1A1\;|\;0A0\;|\;B\;|\;\#\;|\;\epsilon$ and $B \rightarrow\; \#A\#$ – Altaïr Nov 28 '14 at 6:26
• @YuvalFilmus $A \rightarrow 1A1\;|\;0A0\;|\;0A1\;|\;1A0\;|\;B\;|\;\epsilon$ and $B \rightarrow \#A\#$ – Altaïr Nov 28 '14 at 6:41
• Why would you ever create two $\#$ for Yuval's example? – Raphael Nov 28 '14 at 7:43
• @Raphael I am not. The grammar I created is for the language in the question. Is it right ? – Altaïr Nov 28 '14 at 16:44