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

  • Thread starter Thread starter Julio1
  • Start date Start date
  • Tags Tags
    Regular
Click For Summary
If a language \( L \) is regular, then its reverse \( L^R \), defined as \( L^R = \{ w^R \mid w \in L \} \), is also regular. This can be demonstrated in two main ways. First, by utilizing a regular expression \( r \) that generates \( L \), one can construct a new expression for \( L^R \) through recursive transformation based on the structure of \( r \). Second, by taking a deterministic finite automaton (DFA) that accepts \( L \), one can reverse the direction of all transitions, introduce a new initial state, and create \( \varepsilon \)-transitions from this new state to all original accepting states. Both methods effectively show that the reverse of a regular language remains regular.
Julio1
Messages
66
Reaction score
0
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.
 
Technology news on Phys.org
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.
 

Similar threads

Replies
18
Views
3K
Replies
15
Views
4K
Replies
7
Views
2K
Replies
10
Views
7K
Replies
8
Views
2K