Palindrome

languages

Definition

Palindrome

A string is called palindrome iff:

$$w=w^r$$

where $w^r$ is the mirror image of $w$.

Examples

Testing whether a language is regular

Let $L$ be a regular language. The following languages are defined from $L$:

$$L_1=\{w^r\mid w\in L\}$$ $$L_2=\{w{w}^r\mid w\in L\}$$ $$L_3=\{www\mid w\in L\}$$

Then the task is to determine whether each $L_i$ is regular.

• $L_1$ is regular, because regular languages are closed under reversal.
• $L_2$ need not be regular, because the operation $w\mapsto w{w}^r$ is not a closure property of regular languages.
• $L_3$ need not be regular, because the operation $w\mapsto www$ is not a closure property of regular languages.