Search code examples
regular-languagefsm

Cnnverting FSM to regular expression

I know how to convert regular expression into FSM but not exactly sure how to reverse it.

enter image description here

what would the regular expression for this example be?

Solution

  • Regular expression for your DFA will is (b + ab*a)*

    The language description: Symbol b can appear in any fashion but restriction is a can to be for even number of times in language strings.

    (b + ab*a)*
   ^   ^  ^
   |   |  "* because loop on initial state"  
   |   | "* on b because of self loop with label b on 2nd state"
   |
   |"+ because two outgoing edges, One is self loop other via 2nd state"


Here: + means Union, * means repetition for zero or more times

    Note: Language string examples: {^, b, aa, bababb...}

    (even as and any bs including null)