死んだ状態や余分な状態のDFAを生成する正規表現

Question

私のレクサーにDFAミニマイザを実装しようとしていますが、DFAを作成することはできません。表現。

私は、後置式の正規表現からThomson構造を使用して構築されたNFAからDFAを構築しています。それはドラゴンの本に描かれているものとほぼ同じです。レクサーを作成するために、いくつかのNFAは、開始状態からのイプシロン遷移を使用して結合される。 DFAアルゴリズムが適用されているのは、この結合されたNFAです。

DFAを生成する「既知の」正規表現はありますか？死んだ状態の除去と状態の最小化のための素晴らしいテストベッドを作るでしょうか？

もちろん、奇妙なDFAをハックアップしてアルゴリズムを適用することはできますが、それは本当に適切なテストケースではありませんか？私がDFAを構築しているメソッドが死んでいる状態にならないようにするならば、その情報はまったく価値があります。それ以来、私は状態除去機能を完全に実装することをスキップできます。

編集：あなたは正確に答えるために、実装の詳細を必要とする場合、コードは、特にNFA.csとDFA.csクラスgithubで提供されています。さらに、私が使用している構築アルゴリズムについては、blog postsというシリーズを書いています。

Answer 1

わかりましたので、私は完全に丸い方法でこれを見つけました。私は正規表現を視覚化するためのツールを作った。なぜなら私のパーサーからかなりのデバッグ出力が得られたからだ。ツールに示さ(a+b+c+)+|abc

：これは適切に標準トンプソン構成技術を使用すると、あなたはかなり愚かなオートマトンを与えるような表現を示してhttp://regexvisualizer.apphb.com/?Regex=%28a%2Bb%2Bc%2B%29%2B%7Cabc&NfaSize=300&DfaSize=250#

このツールは、現在、任意の最適化をせずにまっすぐトンプソンの構築を行います。完全に余分な式の一部分を削除すると、式は同じままになります。それはしません。