webstation plus

 オートマトン理論と形式言語理論ってよくわからないですよね。

 とはいえ、情報科学や数学、言語学や認知科学などの重要な基礎理論なので、「わからない!」で済ませておくわけにはいきません。

 そんな情報科学初心者におすすめなのが『白と黒のとびら』。ストーリーを楽しんでいるうちに、いつの間にかオートマトン理論と形式言語理論の概要が理解できます。

 オートマトン理論とは?

 大雑把に言えば、抽象的な計算機のモデルです。

 抽象的なモデルなので、目に見えたり、手に触れるような形で存在しているわけではありません。

 コンピュータや自動販売機、自動ドア、からくり人形といった機械の「動作」や、私たち人間が行う「手続き的な行為」から、それらに共通する「計算機的な性質」を抜き出し、書き表したものです。

 オートマトンはいくつかの状態があり、その中には「初期状態」と「終了状態」があります。オートマトンに「記号」を入力すると、オートマトンの状態が変わります(「状態遷移」と言います)。

 もっとも単純なオートマトンでは、次にどの状態に遷移するかは、現在の状態と入力される記号の組み合わせによって決まります。

 物語では、状態を「遺跡の各部屋」、初期状態を「入口の部屋」、終了状態を「出口の部屋」、入力される記号を「扉」として表し、遺跡を探検する主人公とともに謎解きが楽しめます。

 形式言語理論とは?

 形式言語とは、文字列の集合のことです。たとえば、「あいうえお」や「abcdef」、「1111」などがそうです。

 ただし、思っていることを表現したり、他人に伝えるための言語ではなく、特定の文字列からなる列を集めたものは、全て「形式言語」と見なします。

 物語では、この言語を白丸と黒丸の組み合わせで表しています。

 なぜ勉強する必要があるのか?

 では、なぜオートマトン理論と形式言語理論を勉強する必要があるのでしょうか。

 それは以下の問いに答えられるようになるためです。

①「計算」とはそもそも何なのか?
②「計算機」にできること、できないことの境目はどこにあるか?
③人間の脳を一種の「計算機械」と見なした場合、私たちの持つ言語能力をどのように説明することができるか?

 もちろん、本書を読むだけで全てに解答できるわけではありませんが、その大枠はイメージできるようになります。

 魔術師を目指す物語の主人公と一緒に、謎だらけの洞窟や塔を攻略しながらオートマトン理論と形式言語理論に触れてみてはどうでしょうか。

 次に読みたい本

 関連記事

当たり前のことから始めよう!?『数学ガールの秘密ノート/整数で遊ぼう』

(※『数学ガールの秘密ノート/整数で遊ぼう』表紙より)  「数学をもう一度学び直そう!?」と思って読みはじめた本『数学ガールの秘密ノート』。  第2弾の本作は、前作より少し難しくなっていますが、数学マジックなど楽しく学べ …

導関数の公式を求めるために必要な二項定理の紹介

 ディープラーニングなどの機械学習を理解するには、微分の概念を理解しておく必要があります。そして、微分を理解するには二項定理を理解しておく必要があるんですよね。  そこで今回は、『数学ガールの秘密ノート/場合の数』を参考 …

積と商の微分について簡単に紹介

 この前のエントリで合成関数の微分について紹介しましたが、今回は積と商の微分について紹介します。  積と商の微分は、たとえば、「\(p(x)=f(x) \times g(x)\)」や「\(r(x)=f(x) \div g …

線形代数イロハの「イ」を理解しよう

(※『マンガ 線形代数入門』表紙より)  線形代数をご存知ですか。  高校で行列を習った人も多いと思いますが、少し強引な説明をすると行列を使った演算のことです。  行列を使えば、連立方程式などの問題がパソコンを使って簡単 …

1からnの2乗までの和(二乗和)の求め方を簡単に紹介

 この前のエントリで等差数列・等比数列の一般項とその和の求め方について紹介しましたが、今回は\(1\)から\(n^2\)までの和(二乗和)の求め方を『数学ガールの秘密ノート/積分を見つめて』を参考に紹介します。  ディー …

数学が苦手な人に読んで欲しい本『数学ガールの秘密ノート/式とグラフ』

(※『数学ガールの秘密ノート/式とグラフ』表紙より)  数学は得意ですか。  私は学生の頃は得意だったのですが、社会人になってからは苦手意識が強くなりました。複雑な数式が理解できなくなってきたからです。  そこで中学レベ …

AIを正しく理解したいなら最低限知っておきたいこと/『コンピュータ、どうやってつくったんですか?』

 最近、AIに関する話題が多いですよね。ところが、コンピュータの仕組みについてあまり知らない人が語っているケースも多いように思います。  当たり前のことですが、コンピュータがどのような機械なのかを知らなければ、人工知能技 …

等差数列・等比数列の一般項とその和の求め方について紹介

 ディープラーニングなどの機械学習では、たくさんのデータを処理する必要があるため、数の並びをシンプルに表せる数列は頻出のテーマになります。  そこで今回は、『数学ガールの秘密ノート/数列の広場』を参考に、等差数列と等比数 …

『数学する人生』感想/数学者がたどり着いた幸せに生きる方法とは?

 数学者というと堅いイメージがありますよね。世間で騒がれているような些細なことに興味がなく、数学と向き合う日々を過ごしているイメージがあります。  しかし、そんな数学者だからこそ、私たち凡人とは違う視点で「生き方」につい …

合成関数の微分について簡単に紹介

 この前のエントリで微分の公式について紹介しましたが、今回は合成関数の微分について紹介します。  合成関数の微分は、たとえば、\(h(x)=(x^2+3)^6\)などのように、2つ以上の関数の合成で成り立っている関数を微 …