|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 非 ： [ひ] 1. (adj-na,n,pref) faulty- 2. non- ・ 決 ： [けつ] 【名詞】 1. decision 2. vote ・ 定性 ： [ていせい] 【名詞】 1. qualitative 2. stability of a substance ・ 有 ： [う, ゆう] 1. (n,vs) possession ・ 有限 ： [ゆうげん] 1. (adj-na,n) finite 2. limited ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ マトン ： [まとん] (n) mutton, (n) mutton
非決定性有限オートマトン（）または非決定性有限状態機械（）は、有限オートマトンの一種であり、ある状態と入力があったとき、次の遷移先が一意に決定しないことがあるものである。NFAと略記される。 ==直感的説明== NFA は入力文字列を受け付ける。各入力文字を受け付ける度に新たな状態に遷移する。これが全ての文字の入力が終わるまで続く。 非決定性と呼ばれるのは、ある状態からの遷移先が入力文字だけでは一意に定まらない場合があることと、入力文字を受け取らなくても状態遷移する場合があることからである。例えば、状態 S1 にあって文字 a が入力された場合、この文字を受け取らずに状態 S2 に遷移してから a を受け取って状態 S3 に遷移することが可能である。 入力文字を受け取らずに遷移することを「イプシロン遷移」と呼ぶ。一般にギリシャ文字を使って「ε-遷移」と記述する。状態遷移図では、入力文字の代わりに ε を付記する。 最後の入力文字を受け取ったとき、NFA がある特定の状態（受容状態）になった場合のみ、その入力文字列をNFAが受容したと判断される。一方、受容状態以外で終了した場合、その入力文字列は拒否されたと判断される。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「非決定性有限オートマトン」の詳細全文を読む スポンサード リンク
|