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