講座系 オートマトン・言語と計算理論「決定性と非決定性の関係」
本シリーズでは、以下の本に沿って解説を書いている。前回は新しい単元に進んで、非決定性有限オートマトンというものを定義した。前々回までの決定性有限オートマトンとは異なり、同じ記号による遷移先が複数になったり、空集合になったりしてもいいようなも...
講座系
講座系 講座系 オートマトン・言語と計算理論「非決定性有限オートマトン」
本シリーズでは、以下の本に沿って解説を書いている。前回は、有限オートマトンの同型について解説した。これは上の参考書には載っていない内容だが、重要な概念だろうと思い、前回取り扱った。また、同型かつ既約な有限オートマトンは全て同型になる、という...
講座系 オートマトン・言語と計算理論「有限オートマトンの同型」
本シリーズでは、以下の本に沿って解説を書いている。前回は、有限オートマトンの等価と、言語の補集合を認識する有限オートマトンを解説した。等価は今回も使うので、不安なら復習しておこう。以下がその記事だ。さて、今回は…申し訳ないが、再度横道に逸れ...
講座系 オートマトン・言語と計算理論「有限オートマトンの等価と言語の補集合」
本シリーズでは、以下の本に沿って解説を書いている。前回は番外編ということで、有限オートマトンを表現するプログラムを作成した。ちょっと長い記事だが、気になる人は見てみよう。それまでは何をしていたかというと、有限オートマトンについて解説を行って...
講座系 有限オートマトンをプログラムで組んでみた
本シリーズでは、以下の本に沿って解説を書いている。前回まで、有限オートマトンに関するあれこれを書いてきた。有限オートマトン自体の定義は以下の記事。そして、直積オートマトンと、状態の等価性は以下の記事だ。今回は、本筋からちょっと外れて、この有...
講座系 オートマトン・言語と計算理論「直積オートマトンと状態の等価性」
本シリーズでは、以下の本に沿って解説を書いている。前回は、有限オートマトンを解説した。色々と定義したが、細かい単位で見れば難しいことはないはず。不安になったら、それが何を言っていたか、定義を見直してみよう。以下がその記事だ。今回は、前回のラ...
講座系 オートマトン・言語と計算理論「有限オートマトン」
本シリーズでは、以下の本に沿って解説を書いている。前回は、形式言語の形に合わせた正規表現を定義した。今回はちょっとその範囲から外れるが、後でまた戻ってくるので忘れないようにしてほしい。以下がその記事だ。さて、今回は前回解説できなかった有限オ...
講座系 オートマトン・言語と計算理論「正規表現」
前回から、以下の本に沿って解説を書いている。前回は、形式言語というものを扱った。最小単位は記号で、その集合はアルファベット。アルファベットに含まれる記号を並べたものを、そのアルファベット上の列。そして、その列の集合が、形式言語ということだっ...
講座系 オートマトン・言語と計算理論 – 導入「形式言語」
突然だが、プログラムを作りたくなった。やりたいことは、文字列として入力された数式をプログラムで解釈し、計算すること。ただやるだけであれば、BNFを作ってそれをプログラムに落とし込めばいい。そこで、BNFをもう一度しっかり勉強しようとしたら、...
弐寺講座 【弐寺】トリル・デニムはなぜ難しいのか？練習方法は？
以前、弐寺の地力の全体像をまとめた。以下の記事だ。…だいぶ間が空いてしまったが、各個別の記事を書き始めることとしよう。今回は、トリル・デニムについて解説していく。対象はこれらが分からない初心者から、苦手な方まで含める。まずはそもそも本記事で...