講座系 オートマトン・言語と計算理論「正規表現とnfaの関係」
本シリーズでは、以下の本に沿って解説を書いている。前回は、ある言語が正規表現で生成可能なら、それを認識するような\(\varepsilon\)nfaが存在することを示した。こちら側はそこまで難しくなく、理解もしやすかったと思う。以下がその記...
非決定性有限オートマトン
講座系 講座系 オートマトン・言語と計算理論「nfaとεnfaの関係」
本シリーズでは、以下の本に沿って解説を書いている。前回は、またしても新しい有限オートマトンである\(\varepsilon\)入力付き非決定性有限オートマトンを解説した。状態遷移でこれまでに使っていなかった様相やステップといった概念を導入し...
講座系 オートマトン・言語と計算理論「決定性と非決定性の関係」
本シリーズでは、以下の本に沿って解説を書いている。前回は新しい単元に進んで、非決定性有限オートマトンというものを定義した。前々回までの決定性有限オートマトンとは異なり、同じ記号による遷移先が複数になったり、空集合になったりしてもいいようなも...
講座系 オートマトン・言語と計算理論「非決定性有限オートマトン」
本シリーズでは、以下の本に沿って解説を書いている。前回は、有限オートマトンの同型について解説した。これは上の参考書には載っていない内容だが、重要な概念だろうと思い、前回取り扱った。また、同型かつ既約な有限オートマトンは全て同型になる、という...