# Context free Grammar for x1#x2#…#xn

Design a Context-free grammar (CFG) for this language • What are your thoughts on this language? Have you made any progress constructing a grammar? Do you have any ideas at all? – Yuval Filmus May 14 '20 at 6:11

## 1 Answer

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.

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