4月から始める講義、計算数理（オートマトンと形式言語）に関する参考文献をこちらにまとめました。

これはqiitaに掲載した記事と同じ内容です。

はじめに

オートマトンや形式言語の理論は、コンピュータ・サイエンスを学ぶ学生にとっては、（必修ではないが）学ぶことが望ましいコースとしての立ち位置を確立してはいるものの、形式的にすぎるとか、実応用にかけるとか思われがちであるとも思う。しかし、最近のAIブームな世の中に、計算機ができることが何か？という問題は重要になっており、もう一度（古典を）学び直すことは有意義ではないかと思っている。実際に、川添愛さんが童話仕立てな物語にする試みがあったり、高岡詠子さんがブルーバックスを比較的最近（2014年）に出したりと、世の中から少し思い出されているのではないだろうか。

そこで

最近、どんな情報が世の中に出ているのか調べてみた。すると、この分野のバイブル的な書籍である、オートマトン言語理論 計算論の著者であるスタンフォード大学Jeff Ullman氏のホームページから、講義スライドや演習と解答等がダウンロードできるではないか（だいぶ前からではあるが）。素晴らしい時代になったものである。そこで、その講義スライドから、「なぜオートマトンを学習するのか」というさわりの部分が参考になりそうなので、抜粋し日本語にしてみた。

以下、「なぜオートマトンを学習するのか」の超訳

CS154（オートマトンと複雑さの理論入門）の授業にようこそ。なぜオートマトンを学習するのかについて説明しよう。スタンフォード大学の卒業後5年の卒業生に対して、どの授業が彼らの仕事に役に立ったかに関する調査がある。もちろん、CS106（Javaプログラミング入門）のような基礎的な授業は当然トップの座にくるものの、選択授業の中では、CS154は傑出して高くなっている。例えば、AIに比べても3倍のスコアである。

では、どうしてそうなったのだろう。まず、正規表現は多くのシステムで使われている。例えば、UNIX（a. *b等）や、XMLタグを記述するDTD （person (name, addr, child*)等） があげられる 。有限オートマトンはプロトコルや電子回路をモデル化することができ、その理論はモデルを検証することに利用されている。

文脈自由文法は、基本的に全てのプログラミング言語の構文を記述するのに利用されている（自然言語を記述する重要な役割があることを忘れてはいけないが）。DTDは全体として、実際に文脈自由文法そのものである。

現実の問題に対して、解決策を開発しようとすれば、我々はしばしばソフトウェアができることの限界に直面することになる。例えば、決定できない（Undecidable）ものごと – どんなプログラムによっても扱うことができないこと、手に負えない（Intractable）ものごと – プログラムは存在するが高速に処理することはできないこと、がある。CS154は、そのような場合にあなたの道具となる。

CS154を学ぶことによって、我々は離散システムを形式的に扱う方法を学ぶことができる。あなたは、あるプログラムが正しいと証明することはきっとないだろうが、なぜトリッキーなテクニックが本当に有効になっていることを考える必要はでてくるだろう。そして、我々は抽象的なモデルとそれを構築する経験を得ることができる。階層化されたソフトウェアのアーキテクチャをモデル化できる。

おわりに

思ったほど、新しい情報はなかったかもしれないが、ご参考まで…。ちなみに、オートマトン言語理論 計算論は、英語では第3版が出ていて、それで授業をやっているらしい。日本語化はまだだと思う。第1版は数学的なドライな記述の歯ごたえのあるものだったが、第2版はサンプルをプログラムで例示したり大分イメージが変わっていた。第3版はどうなっているのかは、これから確認してみたい。また、今回調べた中で丸岡先生の新しい本もコンパクトで良いと思った。