0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ You can define an automata for $L$ with a single terminating state. Then just reverse the arrows and exchange the starting state with the terminating state. $\endgroup$
    – Berci
    Oct 18, 2021 at 20:17

1 Answer 1

Reset to default
2
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ This makes a lot of sense. Thank you $\endgroup$
    – ryansl39
    Oct 20, 2021 at 17:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .