2

以前、私はここで、有限オートマトンの遷移グラフを正規表現に変換するための助けを求める質問をしました。

この有限オートマトンの正規表現を理解（および形成）する

ユーザーPatrick87のおかげで、探していたヘルプを見つけることができました。私はまた、彼が彼の答えで言及した次のリンクを読みました：

http://krchowdhary.com/toc/dfa-to-reg-exp.pdf

これは、正規表現を見つけるための3つのアルゴリズム手法を説明しています。直感的に、私はBrzozowski代数法に惹かれ、上部に記載されている前回の投稿で助けを求めていたFAを解決しようとしました。

以下は私がFAのために作った特性方程式です。私が間違っている場合は教えて訂正し、正しい方向に向けてください！

R1 = bR2 + aR3

R2 = aR2 + bR4

R3 = aR3 +bR2+λ

R4 = aR4 + bR3

これらは正しいですか？はいの場合、すべてのRiはRjに関してi≠jであるため、どのように置換を行うのですか。

助けてください：D

4

1 に答える 1

3

私はこれを突き刺します...最初に各方程式を減らして、自分自身を含む式に等しいRiがないようにします...

R1 = bR2 + aR3
R2 = a*bR4
R3 = a*bR2 + a*
R4 = a*bR3

さて、置換のために...最初にR4を排除します

R2 = a*ba*bR3

今、私たちはR2を取り除きます

R1 = ba*ba*bR3 + aR3
R3 = a*ba*ba*bR3 + a*

R3を独自のRHSにしたくない...

R3 = (a*ba*ba*b)*a*

ここでR3を削除します

 R1 = ba*ba*b(a*ba*ba*b)*a* + a(a*ba*ba*b)*a*

これは正しく見えます。そのため、私たちはそれをあなたのものに変えることができます。この演習を試してください。

于 2012-01-14T14:30:05.273 に答える