regex - NFA が否定正規表現を実装する方法

Question

NFA を使用して否定正規表現を実装しようとしています。

ab a|bNFA はとのような正規表現を簡単に組み合わせることができることを知っています。a*

そしてその多様[ab]性はに変換することができますa|b

[^ab]しかし、どうすればNFAフラグメントに変換できますか?

Answer 1

これは単なる文字クラスです。NFA の遷移は、1 文字またはラムダ (空の文字列) でラベル付けされます。文字クラスを実装するには、クラス内の各文字のトランジションを用意するだけです。否定されたクラスは、クラスにない文字ごとに 1 つのトランジションで実装されています。NFA は有限のアルファベットを持つ必要があるため、これはまったく問題ありません。A がアルファベットで [^ab] が必要な場合は、セット A - {a, b} 内の文字ごとに 1 つのトランジションが必要です。