CFG atau Context Free Grammar adalah tata bahasa formal di mana setiap aturan produksi adalah dalam bentuk A → B di mana A adalah pemproduksi, dan B adalah hasil produksi. Batasannya hanyalah ruas kiri adalah sebuah simbol variabel. Dan pada ruas kanan bisa berupa terminal, symbol, variable ataupun ɛ, Contoh aturan produksi yang termasuk CFG adalah seperti berikut ini:

  • X → bY | Za
  • Y → aY | b
  • Z → bZ | ɛ

CFG adalah tata bahasa yang mempunyai tujuan sama seperti halnya tata bahasa regular yaitu merupakan suatu cara untuk menunjukkan bagaimana menghasilkan suatu untai-untai dalam sebuah bahasa.

CFG perlu disederhankan dengan tujuan untuk melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi tak berarti. Berikut merupakan langkah-langkah dalam melakukan penyederhanaan CFG:

  • Eliminasi ɛ-production
  • Eliminasi unit production
  • Eliminasi useless symbol

Berikut contoh Penyederhanaan CFG:

A → cAB | ab
B →  BaC| C
C →  bC| ɛ 

Step 1 – Eliminasi ɛ-production

  • Hilangkan semua hasil produksi yang ɛ
  • Jika X → ɛ, maka X adalah nullable
  • Jika Y → X, maka Y adalah nullable
  • Jika Z → Xa, maka Z → a

Result :

A → cAB | ab | cA
B →  BaC| C | Ba | aC | a
C →  bC| b

Step 2 – Eliminasi unit production

  • Jika ada hasil produksi yang terdiri dari 1 variable, maka hasil produksi tersebut disubstitusi dengan hasil produksi dari grammar dimana variable tersebut menjadi pemproduksiResult :
    A → cAB | ab | cA
    B →  BaC| bC | b | Ba | aC | a
    C →  bC| b

Step 3 – Eliminasi useless symbol

  • Uji Generate
    Jika X → YZ, Y → aa, Z → b, maka X,Y,Z lolos uji generate
    Jika M → PQ, P → aa, Q → QQ, maka M dan Q tidak lolos uji generate
  • Uji Reachable
    Jika S → TU dimana S adalah start symbol maka T dan U lolos uji reachable

Final Result :

A → cAB | ab | cA
B →  BaC| bC | b | Ba | aC | a
C →  bC| b