非決定性有限オートマトンとは? わかりやすく解説

Weblio 辞書 > 同じ種類の言葉 > 情報 > コンピュータ > オートマトン > 非決定性有限オートマトンの意味・解説 

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

(Nondeterministic finite automaton から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/04/27 07:44 UTC 版)

非決定性有限オートマトン(ひけっていせいゆうげんオートマトン、: nondeterministic finite automatonNFA)または非決定性有限状態機械(ひけっていせいゆうげんじょうたいきかい、: nondeterministic finite state machine)は、有限オートマトンの一種であり、ある状態と入力があったとき、次の遷移先が一意に決定しないことがあるものである。

直感的説明

NFA は入力文字列を受け付ける。各入力文字を受け付ける度に新たな状態に遷移する。これが全ての文字の入力が終わるまで続く。

M はふたつのDFAの和集合のようになっている。ひとつのDFAは状態 {S2, S1} を持ち、もうひとつは状態 {S3, S4} を持つ。

最終状態 S1 にあるとき、それまでの入力文字列に偶数個の 0 が含まれていたことを意味し、状態 S2 にあるときは奇数個であることを意味する。1 が入力されたとき、上のオートマトンの状態は変化しない。Mが受理されたとき、入力文字列に偶数個の 0 が含まれていた事がわかる。
最終状態 S3 にあるとき、それまでの入力文字列に偶数個の 1 が含まれていたことを意味し、状態 S4 にあるときは奇数個であることを意味する。0 が入力されたとき、下のオートマトンの状態は変化しない。Mが受理されたとき、入力文字列に偶数個の 1 が含まれていた事がわかる。

Mの言語は以下の正規表現で記述される正規言語である。





非決定性有限オートマトンと同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「非決定性有限オートマトン」の関連用語

非決定性有限オートマトンのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



非決定性有限オートマトンのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの非決定性有限オートマトン (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS