講座系 オートマトン・言語と計算理論「非決定性有限オートマトン」 本シリーズでは、以下の本に沿って解説を書いている。 前回は、有限オートマトンの同型について解説した。 これは上の参考書には載っていない内容だが、重要な概念だろうと思い、前回取り扱った。 また、同型かつ既約な有限オートマトンは全て同型になる、... 2020.12.11 講座系
講座系 オートマトン・言語と計算理論「有限オートマトンの同型」 本シリーズでは、以下の本に沿って解説を書いている。 前回は、有限オートマトンの等価と、言語の補集合を認識する有限オートマトンを解説した。 等価は今回も使うので、不安なら復習しておこう。 以下がその記事だ。 さて、今回は…申し訳ないが、再度横... 2020.12.08 講座系
講座系 オートマトン・言語と計算理論「有限オートマトンの等価と言語の補集合」 本シリーズでは、以下の本に沿って解説を書いている。 前回は番外編ということで、有限オートマトンを表現するプログラムを作成した。 ちょっと長い記事だが、気になる人は見てみよう。 それまでは何をしていたかというと、有限オートマトンについて解説を... 2020.12.05 講座系
講座系 有限オートマトンをプログラムで組んでみた 本シリーズでは、以下の本に沿って解説を書いている。 前回まで、有限オートマトンに関するあれこれを書いてきた。 有限オートマトン自体の定義は以下の記事。 そして、直積オートマトンと、状態の等価性は以下の記事だ。 今回は、本筋からちょっと外れて... 2020.12.04 講座系