以上で形式言語理論の入門内容を一通り見ました。お疲れ様でした。
形式言語はどのようなことに使われるのか？という問いからはじめ、文書検索やプログラミング言語に使われることをみました。次に、形式言語が決定性有限オートマトンを使って定義される様をみました。これにより数学的に形式言語を議論できるようになりました。決定性有限オートマトンの変種として非決定性有限オートマトンをみました。一見、非決定性有限オートマトンは決定性有限オートマトンよりも機能が多そうですが、実は両者は等価であることをみました。これらが認識できる言語を正規言語というのでした。正規言語では正規演算という演算により新しい正規言語を構築でき、それを式で表す正規表現を使うと複雑な言語が簡単な式で表現できました。正規表現は文書検索などで実際に応用されています。最後に、この章ではポンピング補題を使って言語が正規言語ではないことを示す技法について学びました。
正規言語についてはこの講義でほぼマスターしたと言っても良いですが、世の中には正規言語以外の言語もあります。特に、文脈自由言語は大抵の形式言語理論の講義で扱われる重要なトピックです。今回は簡潔さを優先するため、この記事には含めませんでした。文脈自由言語については別の機会に新たな記事で紹介したいと思います。知りたい方はそれまで待っていただくか、以下の読書案内をご参照ください。
形式言語理論を学ぶのに有用な本をいくつか紹介します。
こちらの本は小説の形式をとっており、物語を読んでいくうちに自然と形式言語の知識が身につくという稀有な作品です。
小説も取ってつけたようなものではなく、ストーリーとしても面白い。一方で、形式言語についても詳しく扱われているという奇跡のバランスを保っています。
デメリットとしては、ストーリーがある分、最短距離で凝縮された知識を得ることができないことでしょうか。教科書のように要点が整理されている本を期待している人には向いていません。
本腰を入れて形式言語を勉強する前に、形式言語の雰囲気に慣れ親しみたい人にとっては最高の本だと思います。ぜひ手に取ってみてください。
こちらはマイケル・シプサという計算複雑性の大家による伝統的な教科書の一つです。全三巻からなり、第一巻が形式言語について扱っています。各巻は独立しているので、一巻だけ読むといった使い方もできます。
この教科書は解説が丁寧なため、独学にも適しています。また、演習問題も優しいものから骨が折れるものまで非常に豊富です。独学、講義のサブテキスト、輪講、試験対策、あらゆる場面で活躍が期待できます。
この記事の構成についても、こちらの本から強く影響を受けております。
自信をもっておすすめできる名著です。
こちらの本はジョン・ホップクラフト、ジェフェリー・ウルマン、ラジーブ・モトワニという計算機科学の大家によって書かれた世界的に有名な教科書です。上記の「計算理論の基礎」よりも歴史は古く、こちらの方が知名度は高いです。全二巻からなり、第一巻が形式言語について扱っています。
「計算理論の基礎」と比べると、こちらの方が記述量が多く、より網羅的にさまざまなトピックが扱われているように思います。例えば、テキスト検索への応用はこちらの本では扱われていますが、「計算理論の基礎」には扱われていません。
デメリットとしては、分量が多いので学ぶのがその分大変であることがまず挙げられます。「計算理論の基礎」は本当に重要なことに絞って記述しているので、最短コースで学びたい方にはそちらの方がおすすめです。また、第二版の訳出が「計算理論の基礎」よりも昔であるため、訳語が古いように感じる部分もあります。内容に関してはそれ以前に成熟している分野なので、古くなっていることはないです。その点は安心してください。
こちらと迷った場合は「計算理論の基礎」の方をおすすめします。テキスト検索への応用など、幅広いトピックについて知りたい場合は、こちらの本を参照することもおすすめです。
