regular-language - FSM を正規表現に変換する

Question

正規表現を FSM に変換する方法は知っていますが、元に戻す方法は正確にはわかりません。

この例の正規表現は何になるでしょうか?

Answer 1

DFA 意志の正規表現は (b + ab*a)*

言語の説明: 記号bは任意の形式で表示できますが、制限はa言語文字列で偶数回使用できることです。

(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

注: 言語文字列の例:{^, b, aa, bababb...}

( null を含む偶数aおよび任意の )b