変数をわかりやすくするために、名前を付け替える。
G = ( VN, VT, P, S ) をチョムスキー標準形の文法とし、VN= { A1,A2,…,Am } とする。
書き換え規則 Ai → Aj α ( j < i ) に対して、
Aj を左辺にもつすべての書き換え規則 Aj → β について
Ai → β α を書き換え規則の集合に追加して、
すべての書き換え規則 Ai → Aj α について i ≤ j に変換する．
A → A α のように右辺の先頭が左辺に等しい書き換え規則については，
新しい非終端記号 Z を導入して次の置き換えを行う。
A → A α1, A → A α2, …, A → A αr
を A が左辺と右辺の先頭にある書き換え規則とし、
A → β1, A → β2, …, A → βs
を A が左辺にある残りの規則とすると，
これらの規則を新しい非終端記号 Z を使った次の規則で置き換える。
A → βi, A → βi Z ( 1 ≤ i ≤ s )
Z → αi, Z → αi Z ( 1 ≤ i ≤ r )
以上の手順で作られた書き換え規則の右辺の先頭に非終端記号 A があるときは，
それを左辺にもつすべての規則 A → α の右辺で置き換えた規則と置き換えていく。
これを繰り返すことでグライバッハの標準形が得られる。
以下の文法を、Greibachの標準形に直せ。
S → A A | 0
A → S S | 1
まず、S = A1 , A = A2 とします。
すると、問題の文法は、
1) A1 → A2 A2
2) A1 → 0
3) A2 → A1 A1
4) A2 → 1
となります。
手順の２にあてはまる規則は、3)の A2 → A1 A1 、α は右側の A1 となります。
A1 を左辺に持つ規則は 1),2)ですので、β は A2 A2 , 0 になりますね。
んだで、上の文法の 3) の代わりに、
5) A2 → A2 A2 A1
6) A2 → 0 A1
を生成規則に入れます。
この時点で文法はこうなっています。
1) A1 → A2 A2
2) A1 → 0
4) A2 → 1
5) A2 → A2 A2 A1
6) A2 → 0 A1
次、手順の３。
左辺と右辺の先頭が等しい規則は、先ほど作った 5) ですね。
この A2 を左辺に持つ残りの規則は、
4) A2 → 1
6) A2 → 0 A1
DEATH! 上の手順のように名前をつけると
α1 = A2 A1
β1 = 1
β2 = 0 A1
新しい非終端記号 Z を使って
7) A2 → 1
8) A2 → 1 Z
9) A2 → 0 A1
10) A2 → 0 A1 Z
11) Z → A2 A1
12) Z → A2 A1 Z
ではこれで 5) 4) 6)を置き換えると、
1) A1 → A2 A2
2) A1 → 0
7) A2 → 1
8) A2 → 1 Z
9) A2 → 0 A1
10) A2 → 0 A1 Z
11) Z → A2 A1
12) Z → A2 A1 Z
んじゃ手順４。
1) を書き換える。
13) A1 → 1 A2
14) A1 → 1 Z A2
15) A1 → 0 A1 A2
16) A1 → 0 A1 Z A2
11)を書き換える。
17) Z → 1 A1
18) Z → 1 Z A1
19) Z → 0 A1 A1
20) Z → 0 A1 Z A1
12)を書き換える。
21) Z → 1 A1 Z
22) Z → 1 Z A1 Z
23) Z → 0 A1 A1 Z
24) Z → 0 A1 Z A1 Z
では、最終的な文法は。
2) A1 → 0
7) A2 → 1
8) A2 → 1 Z
9) A2 → 0 A1
10) A2 → 0 A1 Z
13) A1 → 1 A2
14) A1 → 1 Z A2
15) A1 → 0 A1 A2
16) A1 → 0 A1 Z A2
17) Z → 1 A1
18) Z → 1 Z A1
19) Z → 0 A1 A1
20) Z → 0 A1 Z A1
21) Z → 1 A1 Z
22) Z → 1 Z A1 Z
23) Z → 0 A1 A1 Z
24) Z → 0 A1 Z A1 Z
これを、元の変数名に直す。
S → 0
S → 0 S A
S → 0 S B A
S → 1 A
S → 1 B A
A → 0 S
A → 0 S B
A → 1
A → 1 B
B → 0 S S
B → 0 S B S
B → 0 S S B
B → 0 S B S B
B → 1 S
B → 1 B S
B → 1 S B
B → 1 B S B
間違ってるかもしれないけどね（ぉ