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.

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

Your Answer

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

Browse other questions tagged or ask your own question.