非決定性有限オートマトン

NDFAでは、特定の入力シンボルに対して、マシンはマシン内の状態の任意の組み合わせに移行できます。つまり、機械が移動する正確な状態を特定することはできません。したがって、それは呼ばれますNon-deterministic Automaton。状態の数が有限であるため、マシンはと呼ばれますNon-deterministic Finite Machine または Non-deterministic Finite Automaton

NDFAの正式な定義

NDFAは、5タプル(Q、∑、δ、q 0、F)で表すことができます。

  • Q は有限の状態のセットです。

  • アルファベットと呼ばれる記号の有限集合です。

  • δは遷移関数です。ここで、δ:Q×∑→2 Q

    (ここでは、Q(2 Q)のべき集合が採用されています。これは、NDFAの場合、状態からQ状態の任意の組み合わせに遷移する可能性があるためです)

  • q0任意の入力が処理されるから初期状態である(Q 0 ∈Q)。

  • F Qの最終状態/状態のセットです(F⊆Q)。

NDFAのグラフィック表現:(DFAと同じ)

NDFAは、状態図と呼ばれる有向グラフで表されます。

  • 頂点は状態を表します。
  • 入力アルファベットでラベル付けされた円弧は、遷移を示します。
  • 初期状態は、空の単一の入力アークによって示されます。
  • 最終状態は二重丸で示されます。

Example

非決定性有限オートマトンを→

  • Q = {a、b、c}
  • ∑ = {0、1}
  • q 0 = {a}
  • F = {c}

以下に示す遷移関数δ-

現状 入力0の次の状態 入力1の次の状態
A a、b b
b c 交流
c b、c c

そのグラフィック表現は次のようになります-

DFAとNDFA

次の表に、DFAとNDFAの違いを示します。

DFA NDFA
状態からの遷移は、入力シンボルごとに1つの特定の次の状態になります。したがって、それは決定論的と呼ばれます。 ある状態からの遷移は、入力シンボルごとに複数の次の状態になる可能性があります。したがって、それは非決定論的と呼ばれます。
空の文字列遷移はDFAでは見られません。 NDFAは、空の文字列遷移を許可します。
DFAではバックトラックが許可されています NDFAでは、バックトラックが常に可能であるとは限りません。
より多くのスペースが必要です。 必要なスペースが少なくて済みます。
文字列は、最終状態に移行する場合、DFAによって受け入れられます。 すべての可能な遷移の少なくとも1つが最終状態で終了する場合、文字列はNDFAによって受け入れられます。

アクセプター、分類子、およびトランスデューサー

アクセプター(レコグナイザー)

ブール関数を計算するオートマトンは、 acceptor。アクセプターのすべての状態は、与えられた入力を受け入れるか拒否するかのいずれかです。

分類子

A classifier 3つ以上の最終状態があり、終了時に単一の出力を提供します。

トランスデューサー

現在の入力および/または前の状態に基づいて出力を生成するオートマトンは、 transducer。トランスデューサーには2つのタイプがあります-

  • Mealy Machine −出力は、現在の状態と現在の入力の両方に依存します。

  • Moore Machine −出力は現在の状態のみに依存します。

DFAおよびNDFAによる受容性

文字列を完全に読み取った後、初期状態で開始するDFA / NDFAが受け入れ状態(最終状態のいずれか)で終了する場合、文字列はDFA / NDFAによって受け入れられます。

文字列Sは、DFA / NDFA(Q、∑、δ、q 0、F)によって受け入れられます。

δ*(q0, S) ∈ F

言語 L DFA / NDFAによって受け入れられます

{S | S ∈ ∑* and δ*(q0, S) ∈ F}

文字列S 'はDFA / NDFA(Q、∑、δ、q 0、F)によって受け入れられません。

δ*(q0, S′) ∉ F

DFA / NDFAによって受け入れられない言語L '(受け入れられた言語Lの補集合)は

{S | S ∈ ∑* and δ*(q0, S) ∉ F}

Example

図1.3に示すDFAについて考えてみましょう。DFAから、許容可能な文字列を導出できます。

上記のDFAで受け入れられる文字列:{0、00、11、010、101、...........}

上記のDFAで受け入れられない文字列:{1、011、111、........}