講座系 オートマトン・言語と計算理論「直積オートマトンと状態の等価性」
本シリーズでは、以下の本に沿って解説を書いている。 前回は、有限オートマトンを解説した。 色々と定義したが、細かい単位で見れば難しいことはないはず。 不安になったら、それが何を言っていたか、定義を見直してみよう。 以下がその記事だ。 今回は...
形式言語
講座系 講座系 オートマトン・言語と計算理論「有限オートマトン」
本シリーズでは、以下の本に沿って解説を書いている。 前回は、形式言語の形に合わせた正規表現を定義した。 今回はちょっとその範囲から外れるが、後でまた戻ってくるので忘れないようにしてほしい。 以下がその記事だ。 さて、今回は前回解説できなかっ...
講座系 オートマトン・言語と計算理論「正規表現」
前回から、以下の本に沿って解説を書いている。 前回は、形式言語というものを扱った。 最小単位は記号で、その集合はアルファベット。 アルファベットに含まれる記号を並べたものを、そのアルファベット上の列。 そして、その列の集合が、形式言語という...
講座系 オートマトン・言語と計算理論 – 導入「形式言語」
突然だが、プログラムを作りたくなった。 やりたいことは、文字列として入力された数式をプログラムで解釈し、計算すること。 ただやるだけであれば、BNFを作ってそれをプログラムに落とし込めばいい。 そこで、BNFをもう一度しっかり勉強しようとし...