GNF atau Greibach Normal Form merupakan sebuah Context Free Grammar (CFG) yang sudah memenuhi beberapa syarat yaitu sudah berada dalam bentuk CNF atau Chomsky Normal Form, tidak memiliki left recursive dan sudah tidak menghasilkan є. Pada GNF terdapat aturan, pada ruas kanannya yaitu hasil produksinya harua diawali dengan terminal lalu selanjutnya bisa diikuti dengan rangkaian simbol terminal atau variabel lainnya, contohnya adalah sebagai berikut :

  • X → p | qYZ
  • Y → pZ
  • Z → qX

Berikut adalah langkah-langkah pembentukan GNF dari CFG yang sudah dalam bentuk CNF:

  • Aturan level, jika A → B, B → C, C → d, maka A<B<C
  • Eliminasi left recursive dengan formula sebagai berikut:
    A → Ab | c
    Maka berubah menjadi :
    A → βA’ | β
    A → αA’ | α
  • Penyesuaian bentuk GNF dengan melakukan substitusi sehaingga pada setiap hasil produksi diawali dengan terminal

Berikut contoh perubahan bentuk CNF menjadi GNF:

P → QP
Q → PQ | b

Step 1 – Aturan level

P<Q (P sudah sesuai tapi Q tidak sesuai jadi harus disubstitusi)

Result :

P → QP | a
Q → QPQ |  b

Step 2 – Eliminasi left recursive

Q → QPQ | b

Terdapat α yaitu PQ dan  β yaitu b

Result :

P → QP | a
Q → bQ’ |  b
Q’ → PQQ’ |  PQ

Step 3 – Penyesuaian bentuk GNF

Karena hanya hasil produksi Q yang sudah sesuai dengan syarat bentuk GNF. Maka dapat dilakukan subtitusi Q terhadap hasil produksi P dan Q’.

Final Result :

P → bQ’P | bP |  a
Q → bQ’ |  b
Q’ →bQ’P QQ’ |  bQ’P Q | bPQQ’ |  bPQQ’ | aQQ’ |  aQQ’