人間の営みの中で自然に発生した日本語や英語などの言語を「自然言語」と呼ぶのに対し、
特定の目的のために意図的に作られたプログラミング言語のような言語を「形式言語」と呼びます。
形式言語の文法を0型～3型の4つのグループに分類し、それぞれに「句構造文法」、「文脈依存文法」、「文脈自由文法」、「正規文法」という名前を付けました。これを「チョムスキー階層」と呼び、グループの違いは、置き換えルールの制限の違いです。
| タイプ | 形式文法 | 制限 |
|---|---|---|
| 0型 | 句構造文法 | なし |
| 1型 | 文脈依存文法 | a→bにおいて、bの長さがaの長さ以上であること |
| 2型 | 文脈自由文法 | a→bにおいて、aが非終端記号１つだけから成ること |
| 3型 | 正規文法 | a→bにおいて、bが終端記号、または終端記号のあとに非終端記号をつけること |
※ 「a→b」は「aはbである」を表す。
※ 非終端記号とは終わりでない記号、終端記号は終わりである記号。
「○○とは△△である」という“置き換えルール”
形式文法では、置き換え元の「○○」の部分を「非終端記号」と呼び、置き換え先の「△△」の部分を「終端記号」と呼びます。
非終端記号とは「終わりでない」、すなわち「他の記号に置き換えられる」という意味であり、
終端記号とは「終わりである」、すなわち「これ以上は置き換えられない」という意味です。
（「記号」とは単語のことだと考えます。）