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.
Designing CFG for sequences of words of which two arbitrary ones are reversals
formal languages;context free;formal grammars