Part2では，「形式言語」と「オートマトン」を通して，機械が「文」をどのように解釈しているのかについて考えてみよう。
人間の営みの中で自然に発生した日本語や英語などの言語を「自然言語」と呼ぶ。それに対して，特定の目的のために意図的に作られたプログラミング言語のような言語を「形式言語」と呼ぶ。
この形式言語で記述された文を受理する（解釈する）架空の機械を「オートマトン」と呼ぶ。形式言語やオートマトンは，現代のコンピュータ技術の基礎原理の1つであり，様々な場面で応用されている。今回は，このコンピュータにおける「言語」について考えていこう。
「置き換えルール」で定義
形式言語の文法は，どのように定義すればよいだろう。1950年代に米国の言語学者であるノーム・チョムスキーは，「○○とは△△である」という“置き換えルール”の羅列で形式言語の文法を定義する方法を提唱した。これを「形式文法（formal grammar）」と呼ぶ。
形式文法では，置き換え元の「○○」の部分を「非終端記号」と呼び，置き換え先の「△△」の部分を「終端記号」と呼ぶ。非終端記号とは「終わりでない」，すなわち「他の記号に置き換えられる」という意味であり，終端記号とは「終わりである」，すなわち「これ以上は置き換えられない」という意味だ。「記号」とは単語のことだと考えて欲しい。
例えば，図1はシンプルな英語の文章を形式文法で定義したものだ。ここで，矢印（→）は「とは」を表し，縦棒（｜）は「または」を意味している。
この文法によって生成される文は「help me」，「help him」，「catch me」，「catch him」の4つだけだ。学校であたかも“形式言語”のように英語を学んだ皆さんなら，「○○とは△△である」という置き換えルールの羅列で文章を作れることに賛同していただけるだろう。英語の文型と単語を覚え，頭の中で「命令文とは“動詞+目的語”である」，「動詞とは○○である」という置き換えをしながら，英文を書いたり話したりしていたはずだ。
形式言語は4つに分類される
チョムスキーは，形式言語の文法を0型～3型の4つのグループに分類し，それぞれに「句構造文法」，「文脈依存文法」，「文脈自由文法」，「正規文法」という名前を付けた。これを「チョムスキー階層」と呼ぶ（表1）。グループの違いは，置き換えルールの制限の違いだ。
0型から3型に向かって，型の数字が大きくなるほど制限が増えていく。したがって，それぞれの型には「0型⊃1型⊃2型⊃3型」という包含関係がある（A⊃Bは，AがBを含むことを意味する）。
置き換えルールに何ら制限がない0型が最も複雑な言語であり，3型が最も単純な言語だと言える。それぞれの置き換えルールの制限は表1に示した通りだ（詳細は専門書を参照して欲しい）。
最も単純な3型の文は，何かの会員番号のようになる。先ほど示したシンプルな英語の文章は，2型に分類できる。プログラミング言語も2型である。自然言語（正確には自然言語は形式言語ではないが）は，強いて言えば1型に分類できる。0型にならないのは，置き換えルールに制限がないわけではないからだ。
文法はN，T，P，Sで示す
形式言語の文法は数学的な（関数や集合などの表現を使った）モデルで表すことも可能だ。非終端記号をN（non-terminal symbol），終端記号をT（terminal symbol），置き換えルールをP（production rule），最初に置き換える記号をS（start symbol），そして形式文法をG（grammar）とすれば，「G＝（N, T, P, S）」とモデル化できる。
これは，「Gは，NとTとPとSによって定義される」という意味だ。さらに，N，T，Pに属する記号の集合を「｛」と「｝」で囲んで表せば，先ほどのシンプルな英語の文法を図2のようにモデル化できる。学者，特に科学者というものは，こういう表現が好きなのだ。
