コンテンツにスキップ

0353: NFA のシミュレーション

問題

非決定性有限オートマトン（NFA）は、1つの状態と入力文字の組に対して遷移先が複数ありうるオートマトンです。 NFA が文字列を受理するかどうかは、非決定的な分岐をすべて列挙しなくても、「現在いる可能性のある状態の集合」を1文字ずつ更新していけば判定できます（部分集合構成の考え方）。

関数 nfa_accepts(delta, start, accepting, s) を実装してください。

  • delta: 遷移関数を表す辞書。delta[(state, char)] は、状態 state で文字 char を読んだときの遷移先状態の集合です。キーが存在しない組の遷移先は空集合とみなします。
  • start: 初期状態。
  • accepting: 受理状態の集合。
  • s: 入力文字列。
  • 返り値: s を読み終えた時点で到達しうる状態のいずれかが受理状態なら True、そうでなければ False。

ε遷移（文字を消費しない遷移）は扱いません。

制約

  • 状態はハッシュ可能な任意のオブジェクトです（例では文字列）。
  • delta に存在しないキーの組を参照しても KeyError を送出してはいけません。
  • 途中で到達しうる状態集合が空になった場合も、正しく False を返してください。
  • 空文字列は、初期状態が受理状態であるとき、かつそのときに限り受理されます。

例

末尾から2文字目が "1" である 0/1 文字列を受理する NFA でテストします。

>>> delta = {
...     ("q0", "0"): {"q0"},
...     ("q0", "1"): {"q0", "q1"},
...     ("q1", "0"): {"q2"},
...     ("q1", "1"): {"q2"},
... }
>>> nfa_accepts(delta, "q0", {"q2"}, "0110")
True
>>> nfa_accepts(delta, "q0", {"q2"}, "0101")
False
>>> nfa_accepts(delta, "q0", {"q2"}, "10")
True
>>> nfa_accepts(delta, "q0", {"q2"}, "1")
False
>>> nfa_accepts(delta, "q0", {"q2"}, "")
False
>>> nfa_accepts(delta, "q0", {"q0"}, "")
True

発展

部分集合構成により、この NFA と等価な決定性有限オートマトン（DFA）を構築する関数 nfa_to_dfa(delta, start, accepting, alphabet) を実装してください。 DFA の状態は NFA の状態集合（frozenset）で表します。

参考