講座系 オートマトン・言語と計算理論「uvwxy定理/反復補題」
本シリーズでは、以下の本に沿って解説を書いている。前回は、二つ目の標準形であるグライバッハ標準形を紹介した。変換方法が複雑、かつそれによってできる生成規則の数もかなり増えるので、幾つか具体的な例を使って練習しておきたい。以下がその記事だ。さ...
文脈自由言語
講座系 講座系 オートマトン・言語と計算理論「正規言語と文脈自由言語」
本シリーズでは、以下の本に沿って解説を書いている。前回は、cfgを考える時に便利な最左導出と導出木を解説した。まだ便利になる状況がそんなに出てきていないが、今後出てくる…はず。以下がその記事だ。さて、今回は以前扱っていた正規言語との関係につ...
講座系 オートマトン・言語と計算理論「文脈自由文法」
本シリーズでは、以下の本に沿って解説を書いている。前回までで、正規文法編が完了だ。前回はその正規文法の名前の紹介と、正規文法には限界があるよという内容を解説した。以下がその記事だ。さて、今回から新しい内容、参考書で言うと第3章に入る。ここで...