言語を生成する2つの方法

1. すべての単語を一覧表示する
   文字: { a }, 単語: { a, aa }
2. すべての単語を生成するルールを指定する
   non-terminal alphabet: { S, A }, terminal alphabet: { a }, start word: { S } rewriting rules:
   1. S -> a
   2. S -> Aa
   3. A -> a
   この定義によって、
   文字’a‘: S –rule 1–> a　と生成できる　また
   単語’aa‘: S –rule 2–> Aa –rule 3–> aa　として　常に、Sから生成できる

正規言語のルールの例

A -> a
A -> Ba (A -> aB　は同じ)

文脈自由文法のルールの例（右辺の順序の違いを区別）

A -> Ba
A -> aB
A -> aaBBA
正規言語はすべて表現できる。だから　正規言語 < 文脈自由文法 とされている。

※実は括弧を使って入れ子にしていくことで、正規言語で文脈自由文法を網羅することができることが証明されている。つまり正規と文脈自由の違いは、グループ分けの方法によりけり…ということらしい

文脈依存文法のルールの例（左辺、右辺両方の順序の違いを区別）

aAa -> aba
aAb -> aab
文脈自由文法をすべて表現できる。だから　文脈自由文法 < 文脈依存文法