If $$ is regular, will $L' = \{v\in L:\,\exists w\in L: w = v^R\}$ be regular also?

404 Views Asked by At

Let $L$ be any language over $\Sigma = \{a, b\}$. Using $L$, we define a new language $L$ which includes every string $w$ if both $w$ and its reverse $w^R$ are in $L$. Show that $L'$ is regular whenever $L$ is regular.

Above is the question from my textbook, I am struggling to prove it and a push in the right direction would be appreciated.

I simplified it to: If $L$ is regular, show that $L' = \{v\in L:\,\exists w\in L: w = v^R\}$ is also regular.

1

There are 1 best solutions below

1
On

Outline:

  1. For any language $L$, $L\text{ is regular}\iff L^R\text{ is regular}$.

  2. For any languages $L_1, L_2$, $L_1 \text{ is regular} \land L_2\text{ is regular}\implies (L_1\cap L_2)\text{ is regular}$

  3. In your question, $L' = L\cap L^R$