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