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.