第2回 形式言語とオートマトン---「文」のルールを知り，機械に解釈させる前回はアルゴリズムを評価するための計算量理論について解説した。今回は，「形式言語」と「オートマトン」を通して，機械が「文」をどのように解釈しているのかについて考えてみたい。 人間の営みの中で自然に発生した日本語や英語などの言語を「自然言語」と呼ぶ。それに対して，特定の目的のために意図的に作られたプログラミング言語のような言語を「形式言語」と呼ぶ。 この形式言語で記述された文を受理する（解釈する）架空の機械を「オートマトン」と呼ぶ。形式言語やオートマトンは，現代のコンピュータ技術の基礎原理の1つであり，様々な場面で応用されている。今回は，このコンピュータにおける「言語」について考えていこう。 「置き換えルール」で定義 形式言語の文法は，どのように定義すればよいだろう。1950年代に米国の言語学者であるノーム・チョムスキーは，「○○とは△△である」という“置き換えルール”の羅列で形式言語の文法
