講座系 オートマトン・言語と計算理論「正規表現とεnfaの関係その1」
本シリーズでは、以下の本に沿って解説を書いている。前回は、nfaと\(\varepsilon\)nfaで認識できる言語に差がないことを示した。これで、dfa、nfa、\(\varepsilon\)nfaの3つそれぞれで認識できる言語に差がな...
ε入力付き非決定性有限オートマトン
講座系 講座系 オートマトン・言語と計算理論「nfaとεnfaの関係」
本シリーズでは、以下の本に沿って解説を書いている。前回は、またしても新しい有限オートマトンである\(\varepsilon\)入力付き非決定性有限オートマトンを解説した。状態遷移でこれまでに使っていなかった様相やステップといった概念を導入し...
講座系 オートマトン・言語と計算理論「ε入力付き非決定性有限オートマトン」
本シリーズでは、以下の本に沿って解説を書いている。前回は、決定性有限オートマトンと非決定性有限オートマトンそれぞれで、認識できる言語に差がないことを証明した。また、その中で非決定性有限オートマトンを決定性に書き換える方法も解説した。それぞれ...