regex - DFA でマルチステートを使用できないのはなぜですか?

Question

私の質問は、state3 を state2 という名前にすることも、一般的にすることもできますか。州に同じ名前を付けられるのはなぜですか。式の場合、ab+a*a 最初の状態は「a」を取ります。その後、状態 2/状態 3 のいずれかになります。

Answer 1

有限状態マシンは、(とりわけ)一連の状態を含むように定義されているため、各状態を一意に識別することは理にかなっています。状態の命名は、それらが攻撃される順序とは何の関係もありません。

FSM にサイクルが含まれることは珍しくありません。例は、以下の状態テーブルで表される、偶数の 0 を含むバイナリ文字列を受け入れる FSM です。

入力 --> | 0 | 1 |
\/--状態 | | | | |
----------|--------|--------|
状態0 | 状態1 | 状態0 |
状態1 | 状態0 | 状態1 |

州: {state0, state1}
開始状態: state0
受け入れる州: {state0}

その場合、マシンは何度も往復する可能性がありますstate0。state1毎回新しい状態を保持しなければならない場合、マシンの複雑さは無限大に爆発します。

Answer 2

一意に識別可能である限り、状態に好きな名前を付けることができます。

州が異ならない場合は、そもそも 2 つの別々の州であってはなりません。

---

特定の例にはor-ing がないため、正規表現はそのように分岐する DFA を使用することはありません。

しかし、次のような正規表現があるとしましょう

a(bb | cc)abb、または一致することができますacc

abとacは異なる状態であり、それらは互いに区別する必要があり、それらからの出力は異なる結論につながります。

あなたがにいて よりもab得たc場合は、最初に戻らなければなりませんが、もしあなたが状態acにいて よりも得た場合は、cに進んaccで終了します。