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 $\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?

$\endgroup$
3
  • $\begingroup$ Not sure where you get confused. Anyway, can get make a PDA that accepts palindromes? Then you can adapt it to accept $L$. $\endgroup$
    – John L.
    Nov 16, 2018 at 8:15
  • $\begingroup$ like what does mean that two characters can't come twice in a row @Apass.Jack $\endgroup$
    – user8911
    Nov 16, 2018 at 8:21
  • $\begingroup$ 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$. $\endgroup$
    – John L.
    Nov 16, 2018 at 8:29

1 Answer 1

1
$\begingroup$

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.

$\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.