1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I am sorry, that was a mistake from my side. It is corrected now. $\endgroup$ – charel-f Apr 7 '18 at 9:32
  • $\begingroup$ 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? $\endgroup$ – charel-f Apr 7 '18 at 9:34
  • $\begingroup$ Thank you for the clarification of my misconception about some and any. I think I found a solution now. $\endgroup$ – charel-f Apr 7 '18 at 10:58
  • $\begingroup$ @charel-f "Some" and "any" mean roughly the same thing. "Every" and all" are something else. $\endgroup$ – Raphael Apr 7 '18 at 11:09
  • $\begingroup$ @Raphael Usually "some" is clear (like in this description). But "any" can be very confusing: "any $a$ will be followed by a $b$" $\endgroup$ – Hendrik Jan Apr 7 '18 at 14:22
1
$\begingroup$

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.

$\endgroup$

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.