Design a Context-free grammar (CFG) for this language

enter image description here

  • 1
    $\begingroup$ What are your thoughts on this language? Have you made any progress constructing a grammar? Do you have any ideas at all? $\endgroup$ – Yuval Filmus May 14 '20 at 6:11

To understand the idea behind the grammar first consider the Pushdown Automata for this langugage: Non-deterministically choose either the beginning or any $\#$, push the string between the chosen position and the next $\#$ symbol. Again non-deterministically choose another $\#$ and start popping out the symbols in the stack if they match with the current symbol being read. If we reach the next $\#$ and the stack becomes empty, then we have found two positions $\exists i,j : x_i = x_j^R$, and hence the word is in the language.

(I'll suggest you now to stop reading the answer and try writing the grammar on your own)

Grammar (let $\Sigma = \{a,b\}$: \begin{equation} S \rightarrow A\#B|A\#B\#A\\ A \rightarrow aA | bA|\#A|\epsilon\\ B \rightarrow \#\#|aB'a|bB'b\\ B' \rightarrow aB'a|bB'b|\#A\#|\# \end{equation}

*It might be written more succinctly perhaps. You can try that.

  • $\begingroup$ I think it is true, But I'm not sure $\endgroup$ – M.Kasaei May 14 '20 at 6:45
  • $\begingroup$ I think you should try convincing yourself that it is indeed true. If you find out a mistake, leave a comment here. $\endgroup$ – prime_hit May 14 '20 at 6:47

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.