HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Designing a DFA and the reverse of it

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
dfathereversedesigningand

Problem

There is a theorem that says if a language is regular, its reverse is regular as well. How can I draw a DFA that shows if a language is regular, it's regular as well?

Solution

$L^R$ is the reverse of the language $L$ and for designing $L^R$ you must:

  • Reverse all edges in the transition diagram.



  • The accepting state for the LR automaton is the start state for the main automaton.



  • Create a new start state for the new automaton with epsilon transitions to reach of the accept states for the main automaton.



  • Convert this NFA back into a DFA.

Context

StackExchange Computer Science Q#39622, answer score: 19

Revisions (0)

No revisions yet.