How does this language accept all palindromes with the alphabet {a,b}?

3.1k Views Asked by At

$L = \{w \in \{a,b\}^{*}$ such that $w = w^R\}$

It only says that w is the reverse of w.

$L = \{ww^R \in \{a,b\}^{*}$ }$

this one says it accepts all palindromes, but the other one doesn't.

1

There are 1 best solutions below

0
On

The first language consists of all words on $a,b$ that are the same as their reversed-string. Since this is the definition of a palindrome, this language contains all palindromes.

In the second language, we construct palindromes by concatenating a string with its reverse. For example, taking $w = abb$, we note that $abbbba$ is in $L$. Note that while every word in this language is indeed a palindrome, all words in this language are of even length so that the word $bab$, which is a palindrome, is not a member.