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.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I am sorry, that was a mistake from my side. It is corrected now. $\endgroup$
    – charelf
    Apr 7, 2018 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$
    – charelf
    Apr 7, 2018 at 9:34
  • $\begingroup$ Thank you for the clarification of my misconception about some and any. I think I found a solution now. $\endgroup$
    – charelf
    Apr 7, 2018 at 10:58
  • $\begingroup$ @charel-f "Some" and "any" mean roughly the same thing. "Every" and all" are something else. $\endgroup$
    – Raphael ♦
    Apr 7, 2018 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, 2018 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.