形式言語
aabb。
〜 形式言語 について、ある aⁿbⁿ語の話者
形式言語(けいしきげんご)は、有限個の文字(アルファベット)を並べて作れる文字列のうち、どれを口にしてよいかをあらかじめ決めてある言語である。話者は決められた文字列しか言えない。決められていない文字列を言おうとすると、その発話は最初から無かったことになる。どの形式言語にも文法の外側で話す方法が無いので、言い間違いは記録上一度も起きていない。
形式言語の単語は、文字を左から右へ並べたものである。意味は持たないが、話者はそれで困っていない。たとえばアルファベット {a, b} からは a、b、ab、ba、aab と単語をいくらでも作れる。ただし、ある言語の話者が使えるのは、そのうち文法が許したものだけである。どれを許すかで言語が分かれ、話者の暮らし方も変わる。
数学ではこれを「文字列の集合」と呼ぶ。話者のあいだでは同じものを「国語」と呼んでいる。なお、a は b よりわずかに早く発音される。

a をいくつか言ったあと、同じ数だけ b を言う言語。挨拶は ab で始まり、n が大きいほど丁寧になる。目上の人への年始の挨拶では n を百以上にするのが礼儀とされる。話者は a を一つ言うごとに台所の皿を一枚積み、b を一つ言うごとに一枚下ろす。皿がちょうど無くなったところで挨拶が終わる。皿が足りない家では、丁寧さに限りがある。
| 単語 | 意味 | 積む皿 |
|---|---|---|
| ab | おはよう | 1 枚 |
| aabb | こんにちは | 2 枚 |
| aaabbb | こんばんは | 3 枚 |
| aaaabbbb | いつもお世話になっております | 4 枚 |
| ba | (受理されない) | −1 枚 |
| ε | (この言語には無い。n は 1 から数える) | 0 枚 |
隣の町で話される言語をまとめてこう呼ぶ。正規語の話者は、覚えておける事柄が生まれつき有限個しかなく、台所に皿も無い。aⁿbⁿ語で年始の挨拶をされると途中で a の数を忘れ、b が足りないまま返事をしてしまう。その返事は aⁿbⁿ語では受理されず、返事をしなかったのと同じ扱いになる。両町の合同の新年会が毎年静かなのはこのためである。両町のあいだには川が一本流れており、橋の名前はまだ誰も知らない。
正規語では、ある長さより長い単語の真ん中あたりを何度繰り返しても、やはり正しい単語になることが証明されている(ポンピング補題)。話者はこれを利用して、長い単語の途中を好きなだけ伸ばして話す。正規語の朗読会は、開始の時刻だけが決まっている。
長さ 0 の単語を ε(イプシロン)と書く。ε だけでできた言語 {ε} の話者は、黙ることで話をする。黙る長さは問わないので、話者同士の会話がいつ始まっていつ終わったのかは、本人たちにも分からない。
これと取り違えやすいのが、単語を一つも持たない空言語 ∅ である。∅ の話者は、黙っていても話したことにならない。{ε} の話者と ∅ の話者が並んで座っていても外からは区別がつかないが、片方は会話をしていて、もう片方はしていない。両者の通訳は、どちらも何も訳さない点では同じ仕事をし、報酬だけが違う[要出典]。
アルファベットから作れる単語を一つ残らず含む言語。Σ* の話者は何を言っても正しく、言い間違いができない。何を言っても受理されるので、聞き手は「受理された」ということから何も知ることができない。そのため Σ* で交わされた会話は、文法の上では ∅ の会話と同じだけのことしか伝えない。辞書はどの言語のものより厚く、引いても何も分からない。
形式言語の話者は、四階建ての集合住宅に、階ごとに分かれて住んでいる。これをチョムスキー階層という。エレベーターは無い。
最上階の 3 型には正規語の話者が住む。部屋の家具は有限個で、模様替えのたびに同じ配置に戻る。その下の 2 型には aⁿbⁿ語のような文脈自由な言語の話者が住み、各部屋に皿を積む棚が一つずつある。1 型の住人は文脈依存で、同じ単語でも両隣に誰が住んでいるかによって言い方を変える。引っ越しがあると、その階の全員が少しずつ言い方を変える。
1 階の 0 型の住人は、部屋の勝手口から外の通りへテープを伸ばして暮らしている。テープの長さに限りは無い。0 型の住人に何か尋ねると、返事が来ることもあるが、返事が来ないのか、まだ来ていないだけなのかを確かめる方法は無い(停止問題)。管理組合はこの件を議論し続けているが、その議論が終わるかどうかも同じ理由で分からない。
上の階の言語は、どれも下の階の言語に含まれる。このため 3 型の住人は、四つの階すべてに住民票がある。1 階の郵便受けは毎朝あふれている。
この記事も形式言語の一つである。アルファベットはひらがな・カタカナ・漢字・英数字・記号で、この言語に含まれる単語は一つ、すなわちこの記事そのものしかない。単語が有限個の言語はすべて正規語なので、この記事は 3 型の最上階に住んでいる。
したがってこの記事にもポンピング補題が成り立つ。それでも、読者が途中の一節を何度読み返しても、記事は長くならない。補題が効くのはある長さより長い単語だけで、この記事の場合、その長さはこの記事より一文字長いからである。