Welcome to our community

Be a part of something great, join today!

Prove that if L is regular, then L^R is regular

Julio

Member
Feb 14, 2014
71
Prove that if $L$ is regular, then $L^R=\{w^R, w\in L\}$ is regular.

Hello MHB! I need if you can help me with this problem. Thank you.
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,483
One way is to take a regular expression $r$ that generates $L$ and construct an expression that generates $L^R$. It is built by recursion on $r$.

Another way is to take a DFA accepting $L$ and reverse all arrows. One also has to add a new initial state and add $\varepsilon$-transitions from it to all old accepting states.