「白と黒のとびら オートマトンと形式言語をめぐる冒険」を読んで、「オートマトン」と「形式言語」がよく分からなかったからまとめてみる
# 経緯
たまに本屋巡りをすることが趣味の一つなのだが、ジュンク堂のプログラミングの関連書籍のコーナーに陳列されていたのを目にした時から気になっていた本。
初めてこの本を知ってから1年以上経つが、ようやく読むに至った次第。
# 本の内容について
「白と黒のとびら オートマトンと形式言語をめぐる冒険」読了。
— FOOTPRINT (@edat2xt) 2018年7月29日
正直、事前知識がなくて、オートマトンと形式言語についてはよく理解できなかった。
ただ、物語がおもしろく、主人公が成長していく過程が自分がプログラマとして辿ってきた過程と重なり、終盤は喫茶店で一気に読んでしまった。
正直、「オートマトン」や「形式言語」について予備知識がない人が読んでもそれらについてはよくわからないのではないかと思う。
ただ、それらはコンピュータサイエンスに切っても切り離せないものだと思うから、ちょっとまとめてみようと思う。
#「オートマトン」について
##「オートマトン」とは
コンピューターなどの計算機の仕組みを表す数理モデル。コンピューターの本質的な機能や性質の理解のために利用される。これを実現したものに、記号を書いた入力テープと、記号の読み取り装置、状態制御装置のセットがある。テープ上の記号を読み込み、状態制御装置の前の状態と照らし合わせて、内部の状態を変更していく。実用化した例としては、駅の自動改札機などがある。
参考サイト
#「形式言語」について
## 「形式言語」とは
ヒトの思考過程をモデル化し，文字・記号で表した体系。普通にヒトが話したり書いたりする自然言語に対立する概念。形式言語は，要素となる複数個の記号とそれらを結びつける構文規則（文法）からなる。構文規則としてアメリカ合衆国の言語学者アブラム・ノーム・チョムスキーが生成文法という数学的モデルを与えたことにより，コンピュータで使われるプログラム言語と形式言語の関係が生まれた。その理論は，たとえばプログラム言語で書かれたプログラムをどのように機械語に翻訳すればよいかに密接に関係している。さらに計算の理論など，コンピュータ科学の基礎のさまざまなところで形式言語理論は必須の概念となっている。