# 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

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.
Grammar (let $$\Sigma = \{a,b\}$$: $$$$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\#|\#$$$$