「形式言語理論」第7回

• 実施日：2007-06-05(火) 1限
• 講義内容：閉包性を持つ正則言語の演算（4.2節）、反復補題（4.1節）、オートマトンの状態数最小化（4.4節、アイデアのみ）

有限オートマトンや正則表現に関する最後の話題として、正則言語に関する性質を取り上げます。この章で重要なのは、正則言語にどのような演算を施すと正則言語になるのか（閉包性）、どのような言語が正則ではないのか（反復補題）、それにオートマトンの状態数最小化です。

日程の都合上、閉包性に関してはほとんど事実のみを示し、共通部分の証明（直積構成法）のみ概略を示しました。また反復補題についても、正則でない言語の典型例である {0^n 1^n | n ≧ 1} についてのみ概略を示すにとどめました。学問を追究するという意味では不十分ですが、時間を考慮して、アイデアの理解を優先した結果です。興味のある方はテキストなりでより深く勉強していただければと思います。

オートマトンの状態数最小化については、実用上も重要な技術なので、時間を割いて説明するつもりです。まず今日のところは、おおざっぱなストーリーだけ示しました。次回、手法の詳細について説明します。