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