regex - ドットスター正規表現を NFA に変換する

Question

特定の正規表現のセットを単一の NFA に変換していますが、いくつか問題があります。「ab.*c」(「a」、「b」、任意の数の文字、および「c」の一致を表す) などの正規表現を変換するにはどうすればよいですか?

私の最終的な目標は、単一の NFA を DFA に変換することです (そのためにサブセット構築アルゴリズムを使用しています)。

Answer 1

正規表現の A.*は、アルファベットのすべての文字の NFA のループ状態に対応します。

cその状態から受理状態への遷移もあります。

cループ遷移と受け入れ遷移の両方を使用してもまったく問題ありません。そのため、非決定論的です。