講座系オートマトン・言語と計算理論「正規表現とεnfaの関係その1」
本シリーズでは、以下の本に沿って解説を書いている。 前回は、nfaと\(\varepsilon\)nfaで認識できる言語に差がないことを示した。 これで、dfa、nfa、\(\varepsilon\)nfaの3つそれぞ...
有限オートマトン
講座系講座系オートマトン・言語と計算理論「nfaとεnfaの関係」
本シリーズでは、以下の本に沿って解説を書いている。 前回は、またしても新しい有限オートマトンである\(\varepsilon\)入力付き非決定性有限オートマトンを解説した。 状態遷移でこれまでに使っていなかった様相やス...
講座系オートマトン・言語と計算理論「ε入力付き非決定性有限オートマトン」
本シリーズでは、以下の本に沿って解説を書いている。 前回は、決定性有限オートマトンと非決定性有限オートマトンそれぞれで、認識できる言語に差がないことを証明した。 また、その中で非決定性有限オートマトンを決定性に書き換え...
講座系オートマトン・言語と計算理論「決定性と非決定性の関係」
本シリーズでは、以下の本に沿って解説を書いている。 前回は新しい単元に進んで、非決定性有限オートマトンというものを定義した。 前々回までの決定性有限オートマトンとは異なり、同じ記号による遷移先が複数になったり、空集合に...
講座系オートマトン・言語と計算理論「非決定性有限オートマトン」
本シリーズでは、以下の本に沿って解説を書いている。 前回は、有限オートマトンの同型について解説した。 これは上の参考書には載っていない内容だが、重要な概念だろうと思い、前回取り扱った。 また、同型かつ既約な有限オ...
講座系オートマトン・言語と計算理論「有限オートマトンの同型」
本シリーズでは、以下の本に沿って解説を書いている。 前回は、有限オートマトンの等価と、言語の補集合を認識する有限オートマトンを解説した。 等価は今回も使うので、不安なら復習しておこう。 以下がその記事だ。 ...
講座系オートマトン・言語と計算理論「有限オートマトンの等価と言語の補集合」
本シリーズでは、以下の本に沿って解説を書いている。 前回は番外編ということで、有限オートマトンを表現するプログラムを作成した。 ちょっと長い記事だが、気になる人は見てみよう。 それまでは何をしていたか...
講座系有限オートマトンをプログラムで組んでみた
本シリーズでは、以下の本に沿って解説を書いている。 前回まで、有限オートマトンに関するあれこれを書いてきた。 有限オートマトン自体の定義は以下の記事。 そして、直積オートマトンと、状態の等価性は以下の...
講座系オートマトン・言語と計算理論「有限オートマトン」
本シリーズでは、以下の本に沿って解説を書いている。 前回は、形式言語の形に合わせた正規表現を定義した。 今回はちょっとその範囲から外れるが、後でまた戻ってくるので忘れないようにしてほしい。 以下がその記事だ。 ...