Context Free Grammer and PDA (Palindrome but without characters repeating in a row)

Question

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 $\Sigma = \{a, b, c\}$.

Let $L = \{w \in \Sigma^∗| w = w_1w_2\cdots w_n \mbox{ is a palindrome and } w_i \neq w_{i+1} \forall 0 \le i\lt 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?

Answer 1

The language in question consists of all palindromes in which no two consecutive characters are the same. For example, $aa$ is a palindrome, but doesn't belong to the language since $a$ repeats; but $aba$ is OK.

When the alphabet consists only of $a$ and $b$, you can modify the grammar $S \to aSa|bSb|a|b|\epsilon$ of palindromes to accept your language by using two nonterminals $A,B$ which generate the following languages:

• $A$ generates all palindromes starting with $a$ in which no two consecutive characters are the same.
• $B$ generates all palindromes starting with $b$ in which no two consecutive characters are the same.

I'll let you complete the construction, and generalize it to larger alphabets.

(In the particular case of an alphabet of size 2, the language is actually regular, but this doesn't happen when the alphabet is larger.)

The simplest way to construct a PDA is to use to use the production construction: starting with a PDA for the palindrome language and a DFA for the language of strings with no repeated characters, you can construct a PDA accepting the intersection. This is a standard construction that appears in many textbooks.