logo

DFA の例

例 1:

∑ = {0, 1} で FA を設計すると、1 で始まり 0 で終わる文字列が受け入れられます。

解決:

FA は開始状態 q0 を持ち、そこから入力 1 を持つエッジのみが次の状態に進みます。

決定論的有限オートマトンの例

状態q1で1を読み取ると状態q1になりますが、状態q1で0を読み取ると最終状態である状態q2に到達します。状態 q2 で 0 または 1 を読み取ると、それぞれ q2 状態または q1 状態に移行します。入力が 0 で終わる場合は最終状態になることに注意してください。

例 2:

∑ = {0, 1} で FA を設計すると、入力 101 のみを受け入れます。

解決:

決定論的有限オートマトンの例

指定されたソリューションでは、入力 101 のみが受け入れられることがわかります。したがって、入力 101 については、他の入力に対して示される他のパスはありません。

例 3:

∑ = {0, 1} の設計 FA は、偶数個の 0 と偶数個の 1 を受け入れます。

解決:

この FA は、入力 0 と入力 1 に対して 4 つの異なるステージを考慮します。ステージは次のとおりです。

決定論的有限オートマトンの例

ここで、q0 は開始状態であり、最終状態でもあります。 0 と 1 の対称性が維持されることに注意してください。各状態に次のように意味を関連付けることができます。

q0: 0と1が偶数個ある状態。
q1: 0が奇数個、1が偶数個ある状態。
q2: 0が奇数個、1が奇数個ある状態。
q3: 0が偶数個、1が奇数個ある状態。

例 4:

∑ = {0, 1} の設計 FA は、3 つの連続する 0 を含むすべての文字列のセットを受け入れます。

解決:

この特定の言語に対して生成される文字列は、000、0001、1000、10001、... で、0 は常に 3 の塊の中に表示されます。遷移グラフは次のとおりです。

決定論的有限オートマトンの例

トリプル ゼロのシーケンスは、最終状態に到達するまで維持されることに注意してください。

例 5:

DFA の設計 L(M) = {w | w ε {0, 1}*}、W は連続する 1 を含まない文字列です。

解決:

3 回連続して 1 が発生すると、DFA は次のようになります。

決定論的有限オートマトンの例

ここでは、2 つの連続する 1 または 1 つの 1 が許容されます。

決定論的有限オートマトンの例

ステージ q0、q1、q2 が最終状態です。 DFA は、10、110、101、.... など、連続する 1 を含まない文字列を生成します。

例 6:

∑ = {0, 1} で FA を設計すると、偶数の 0 の後に単一の 1 が続く文字列が受け入れられます。

解決:

DFA は、次のような遷移図で示すことができます。

決定論的有限オートマトンの例