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

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?

• Not sure where you get confused. Anyway, can get make a PDA that accepts palindromes? Then you can adapt it to accept $L$. Nov 16 '18 at 8:15
• like what does mean that two characters can't come twice in a row @Apass.Jack Nov 16 '18 at 8:21
• Oh. Did you see how I have updated your question? Check how $L$ is defined. For example, $aba$ and $abcba$ are in $L$. However, $aabaa$ is not in $L$ since $a$ occurs twice in a row. Nor is $aa$. Nov 16 '18 at 8:29

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.