1
$\begingroup$

So this a question from my book and I have to make CFG of this language but I am confused what does it mean when it says

"L contains palindromes that don’t ever have the same character occur twice in a row."

Let Σ = {a, b, c}

Let L = {w ∈ Σ∗| w = {w1, w2, . . . , wn} is a palindrome, and wi 6= wi+1 ∀ 0 ≤ i < n}.

In other words, L contains palindromes that don’t ever have the same character occur twice in a row.

In the second part can someone guide me how to make it's PDA or give an idea.

Improve this question
$\endgroup$
1
  • $\begingroup$ These two questions were exactly the same but I have edited the earlier one for the better. I even suspect the OPs are the same. Please do not repost on the same site, which takes unfair advantage of others as well as wasting the time of people who are helping you. $\endgroup$
    – John L.
    Nov 16, 2018 at 16:00

1 Answer 1

Reset to default
1
$\begingroup$

The grammar $S \to aSa \mid bSb \mid cSc \mid a \mid b \mid c \mid \epsilon$ would generate (normal) palindromes.

A simple way to extend this to generate palindromes with non-repeating would be to add for each letter $x$ a new non-terminal $S_{not\text{-}x}$, and adapt the grammar:

$S \to aS_{not\text{-}a}a \mid \dots$

$S_{not\text{-}a} \to bS_{not\text{-}b}b \mid \dots$

There are probably more efficient ways.

Improve this answer
$\endgroup$

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