CFG & CFL - Materi 6 - Teori Bahasa dan Automata

Context Free Grammar 1 - Materi 6 from ahmad haidaroh

Saudara/i sekalian (berdua deh........asyiiikkkkk).....

Gambar 1. Android Evolution

Kali ini akan disajikan tentang Context Free Grammar (Tata Gramer Bebas) dan Context Free Language (Tata Bahasa Bebas). 

Bahasa pemrograman adalah bahasa wajib yang harus dipakai dalam dunia ICT (information communication and technology).  Karena pada dasarnya semua aplikasi yang terpakai didalam ICT semua menggunakan bahasa pemrograman.  Tak terkecuali android yang sekarang lagi "naik daun" (kalo naik unta dikira di padang pasir).......

Gambar 2. "Bloon Phone"

Ok......CFG adalah tata cara menyusun kalimat dalam pemrograman, sehingga komputer mengerti apa yang diinginkan oleh programmernya. 

Bayangkan saja kalo komputer tidak mengerti apa yang diperintahkan oleh programmer, pasti komputer tidak akan melakukan apa-apa........(kata anak saya, "bapak ni masih juga simpan Bloon Phone".  Ya aku bilang "biarin aja, karena kalo ngga ada "bloon phone" pasti ngga muncul "smart phone").

Bahasa pemrograman pasti mempunyai ciri khas sendiri-sendiri, misalnya
1. Kalau dalam pascal, dikenal Begin, End, read, write
2. di C atau java dikenal { ,  }, System.Out.Println,
3. Basic : DIM, REM, write, print, input, dll

Karena banyaknya perbedaan tersebut, maka untuk membedakan ciri-ciri yang dipunyai dan agar komputer mengenali ini bahasa apa, maka disusunlah CFG.

Context Free Grammar (CFG) terdiri atas sejumlah production yang berbentuk A → α dengan α berupa sejumlah simbol terminal dan non-terminal. Selain contex-free grammar terdapat jenis grammar lain yang disebut context-sensitive grammar (CSG). Perbedaannya dengan CFG adalah pada bentuk production. Bagian head production (simbol di kiri tanda panah) CFG selalu berupa satu simbol non terminal. Bagian head production CSG boleh terdiri atas sejumlah simbol.

Gambar 3. Smart Phone

CFG dituliskan dalam bentuk 4 komponen (4-tupel)

G = (N, S, P, S)

N = himpunan nonterminal.
S = himpunan terminal/ alfabet
P = aturan produksi, yakni A à a
      dengan A Î N, a Î (N È S)*
S = simbol awal

Misalkan : G = ({S}, {a,b}, P, S)

Dengan P adalah :

   S à aSb

   S à ab

Maka :

Turunan yang dihasilkan:

S Þ aSb Þ aabb

S Þ aSb Þ aaSbb Þ aaabbb

S Þ aSb Þ aaSbb Þ aaaSbbb Þ aaaabbbb

Production berikut milik sebuah CFG
1. P → 0P0
2. P → 1P1
3. P → 0
4. P → 1
5. P → ε

Derivasi yang dapat dibentuk diantaranya :

P ⇒ 1P1 ⇒ 10P01 ⇒ 101P101 ⇒ 101101

sentential form 1P1 diturunkan dari sentential form P berdasarkan production 2.
sentential form 10P01 diturunkan dari sentential form 1P1 berdasarkan production 1.
Dan seterusnya

Untuk lebih jelasnya, saya sertakan link presentasi CFG dan CSL berikut :

Presentasi CFG dan CSL 

Terima kasih.