実際の動作を見る
NFA図の例。
同じツールに4つの依頼。以下の図はすべて実際に生成されたものです。
入力する内容
aとb上で、abで終わる文字列だけを受理するNFAを描いてください。q0はaとbでループし、q0はaでq1へ移動でき、q1はbで受理状態q2へ移動します。
次に試す読み終わった入力を拒否するデッド状態を追加してください。対象の接尾辞をabからbaに変更してください。
状態図 · OMG UML 2.5.1 §14 + Harel (1987) statechart · schematex-state
生成された図
NFA図とは。
NFA図は、非決定性有限オートマトンの状態図です。円は状態、矢印は遷移、入ってくる矢印は開始状態、二重円は受理状態を表します。
DFAとは異なり、NFAは同じ入力記号に対して複数の遷移を選べ、入力を消費しないε遷移も使えます。可能な経路の少なくとも1つが受理状態で終われば、その文字列は受理されます。
- Standard
- OMG UML 2.5.1 §14 + Harel (1987) statechart
- Engine
- schematex-state
- Editable
- Double-click text, drag nodes
- Export
- SVG · PNG · PDF
利用者
NFA図を使う人。
機械が接尾辞、接頭辞、部分文字列をどのように認識するかを示す正規言語の演習。
正規表現の和集合を授業ノートで見える形にする、小規模なε-NFAの構成。
実装に変換する前に、分岐として描くトークン接頭辞の候補。
使い方
3ステップでNFA図を作る方法。
01
説明する
まずは1段落で十分です。
“aとb上で、abで終わる文字列だけを受理するNFAを描いてください。q0はaとbでループし、q0はaでq1へ移動でき、q1はbで受理状態q2へ移動します。”
02
図を確認
最適なエンジンで描画します。
03
変更点を伝える
編集のたびにバージョンを保存します。
読み終わった入力を拒否するデッド状態を追加してください。
V2 · DRAWN FROM V1, NOTHING RETYPEDよくある質問
よくある質問
NFAとは何ですか？
非決定性有限オートマトンとは、1つの入力記号に対して複数の遷移候補を持てる有限状態機械です。経路の少なくとも1つが受理状態で終わると受理します。
NFAとDFAの違いは何ですか？
DFAでは、各状態と入力記号の組み合わせに対する次の状態が1つだけです。NFAは複数の状態に分岐でき、ε遷移も含められます。ただし、NFAとDFAが認識できる正規言語の種類は同じです。
ε遷移とは何ですか？
ε遷移は、入力から文字を消費せずに状態を変更する遷移です。正規表現からNFAを構成するとき、分岐を結合したり分けたりするためによく使われます。
受理状態はどう表しますか？
受理状態（最終状態）は二重円で表します。すべての入力を読み終えた後、いずれかの経路がその状態で終わる場合にだけ受理します。
正規表現からNFAを作れますか？
はい。正規表現とアルファベットを説明し、状態図で明示したいグループ化や選択（OR）を指定してください。
関連ツール
