Context free grammar: Meaning of notation ww^R

5k Views Asked by At

A common example in CFG is the palindrome example. These examples often contain the $\ ww^R$ notation for the string.

An example from my class could be:

Strings $\ ww^R$ over the alphabet $\ \Sigma = \{0,1 \} $ (a subset of palindromes over $\ \Sigma $), or

$$\ L=\{ww^R | w = (a + b)^+ \}$$

My confusion lies in the notation $\ w^R $, i don't understand what the purpose of this is.

1

There are 1 best solutions below

1
On BEST ANSWER

$w^R$ is simply the string $w$ reversed. For example, if $w = abb$, then $w^R = bba$. It is easy to see then that the strings of the form $ww^R$ are exactly the palindromes, such as $abbbba$.