# Is it possible to create a CFG with succesive palindromes?

In one of my homework I am requested to find a Context-free-grammar (CFG) and a push down automaton (PDA) for the following language:

$L = \{x_1\#x_2\#...\#x_k | k \geq 2, \text{ each } x_i \in \{a, b\}^*, \text{ and for some } i \text{ and } j, x_i=x_j^\mathcal{R}\}$

My problem is that the statement

$\text{ ... and for some } i \text{ and } j, x_i=x_j^\mathcal{R}\}$,

i.e. any two pairs in the sequence must be each others reverses, forces us to make all $x_i$'s palindromes, as that is the only way any two are guaranteed reverses of each other.

If that interpretation is correct, I think the problem is impossible to solve with a Context free grammar, or not? This leads me to believe I interpreted the statement wrong and it means something else, but I can't figure out what.

A reference to $j$ is missing. My guess is that it should read $x_i=x_j^{\mathcal R}$. This means that some pair $x_i$, $x_j$ should be each others reverse, or one string should be a palindrome. This can be done with a CFG.

(after correction) It does not say that for each $i$ there should be a $j$, it just states that some $i,j$ exist. One pair will do. If the word "any" would have been used then this would probably change the meaning, although "any" sometimes is ambiguous.

• I am sorry, that was a mistake from my side. It is corrected now. – charel-f Apr 7 '18 at 9:32
• You say that one string should be a palindrome, but is the question not phrased in a way that any i and j should be each others reverse, meaning all strings need to be the same palindrome? – charel-f Apr 7 '18 at 9:34
• Thank you for the clarification of my misconception about some and any. I think I found a solution now. – charel-f Apr 7 '18 at 10:58
• @charel-f "Some" and "any" mean roughly the same thing. "Every" and all" are something else. – Raphael Apr 7 '18 at 11:09
• @Raphael Usually "some" is clear (like in this description). But "any" can be very confusing: "any $a$ will be followed by a $b$" – Hendrik Jan Apr 7 '18 at 14:22

I'm trying to answer my own question as I found a grammar that should work based on the help given by the top answer.

$S \to MCN$

$M \to \epsilon \ | \ A\#$

$N \to \epsilon \ | \ \#A$

$A \to \epsilon \ | \ aA \ | \ bA \ | \ A\#A$

$C \to aOa \ | \ bOb \ | \ \# \ | \ aCa \ | \ bCb \ | \ \#O\#$

$O \to \# \ | \ \#A\#$

I think this grammar should work. It is based on my (hopefully) correct assumption that $... \text{ each } x_i \in \{a,b\}^*$ means that $x$ can also be $\epsilon$, as $\epsilon \in \{a,b\}^*$. Thus the language created with $\epsilon\#\epsilon$, which is in fact just $\#$, should be accepted. If that is wrong, please feel free to correct me.