CFG (Contex Free Grammar)

Context Free Grammar (CFG)/ Bahasa Bebas Konteks adalah sebuah tata bahasa dimana tidak terdapat pembatasan pada hasil produksinya, Contoh Pada aturan produksi :

α → β

batasannya hanyalah ruas kiri (α) adalah sebuah simbol variabel. Sedangkan contoh aturan produksi yang termasuk CFG adalah seperti di bawah :

§  B → CDeFg

§  D → BcDe

Context Free Grammar (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.

Ambiguitas

Ambiguitas terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu string.

Misalkan terdapat tata bahasa sebagai berikut :

§  S → A | B

§  A → a

§  B → a

Untuk memperoleh untai ‘a’ bisa terdapat dua cara penurunan sebagai berikut :

§   S => A => a

§   S => B => a

CNF (Chomsky Normal Form)

Bentuk normal Chomsky / Chomsky Normal Form  (CNF) merupakan salah satu bentuk normal yang sangat berguna untuk Context Free Grammar (CFG) . Bentuk normal Chomsky dapat dibuat dari sebuah tata bahasa bebas konteks yang telah mengalami penyederhanaan yaitu penghilangan produksi useless, unit, dan ε. Dengan kata lain, suatu tata bahasa bebas konteks dapat dibuat menjadi bentuk normal Chomsky dengan syarat tata bahasa bebas kontesk tersebut:

Tidak memiliki produksi useless

Tidak memiliki produksi unit

Tidak memiliki produksi ε

Bentuk normal Chomsky (Chomsky Normal Form, CNF) adalah Context Free Grammar (CFG) dengan setiap produksinya berbentuk :

A → BC atau A → a.

TRANSFORMASI CFG KE CNF

Transformasi CFG ke CNF adalah transformasi berikut :

Aturan produksi dalam  bentuk normal Chomsky ruas kanannya tepat berupa sebuah terminal atau dua variabel.

Misalkan:

A → BC

A → b

B → a

C → BA | d

Admin:
Biarlebih mengerti langsung liat video aja gan, jangan lupa like dan subscribe :v