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