regex - 正規表現を**手作業で**単純化するための手法

Question

私はREが

s(bs)*[(abb*a*)*ab]*aa(a∪b)どこs=b*a*ab

に簡略化できます

(a∪b)*abaa(a∪b)、

(ab)*a=a(ba)*しかし、私が知っている、または(a*b)*a*=(a∪b)*効果がないように見えるすべての一般的な変換。

したがって、質問は次のとおりです。

1. ここで段階的な変換プロセスは実行可能ですか？もしそうなら、それがどのように行われるかを教えてもらえますか？
2. 証明のために他のタイプの技術が必要な場合、それらは何ですか？
3. 正式なREを単純化するために使用される手法を説明する明確で包括的なリファレンスはありますか？

ありがとう。

Answer 1

これを行う方法はたくさんあります。

これを行う簡単な方法の1つは、正規表現をNFAに変換することです。2つのNFAが同じ言語を認識するかどうかを確認するには：

1. 両方のNFAの開始状態を考慮してください。

2. 各NFAについて検討している州のイプシロン閉鎖を取ります。

3. 1つのNFAの状態のセットに少なくとも1つの受け入れ状態が含まれているが、他のNFAのセットに受け入れ状態が含まれていない場合、NFAは等しくなく、完了です。

4. それ以外の場合は、シンボルごとに、そのシンボルに従ってNFAごとに新しい状態のセットを取得し、手順1に戻ります。

考慮すべき状態のセットの数には限りがあるため、これには有限のステップ数がかかります。

両方の正規表現を最小のDFAに変換して、それらが同形であることを示すこともできますが、この手法は実際には上記の手法とまったく同じですが、手順が異なります。

図

REaa*とを検討してくださいa*a。それらが同じ言語を認識することは明らかですが、アルゴリズムを説明するためにそれらを使用します。

1. まず、各NFAの開始状態を検討します。これらは{1}、左側のRE{1}用と右側のRE用であり、これを。と記述し{1},{1}ます。

2. 次に、イプシロンクロージャを取得します。これは{1},{1,2}です。

3. どちらのセットにも終了状態が含まれていないため、続行します。

4. 発信シンボルはのみaであるため、すべてのa遷移を取得してを取得します{2},{1,3}。

5. イプシロンクロージャーは{2,3},{1,2,3}です。

6. どちらにも終了状態が含まれているため、続行します。

7. 繰り返しますが、発信シンボルはaであるため、すべてのa遷移を取得してを取得します{2},{1,3}。

8. イプシロンクロージャーは{2,3},{1,2,3}です。これはステップ5と同じなので、再度実行することはありません。

他に調べるものがないので、私たちは完了し、2つは同一であることが証明されました。