Otomata : TATA BAHASA (GRAMMAR) dan POHON DERIVASI

Nemu tutorial dari dosen jaman kuliah soal otomata, share aja ah

1. TATA BAHASA (GRAMMAR)

Bahasa merupakan himpunan kalimat (baik terhingga maupun tak terhingga). Bahasa dapat disajikan dengan menyebut kalimatnya satu persatu. Untuk bahasa tak hingga, penyebutan seperti itu tidak mungkin. Oleh karena itu diciptakan cara penyajian yang mendeskripsikan bahasa secara efisien. Cara penyajian tersebut adalah Tata Bahasa atau Grammar.

Sebuah Tata Bahasa (Grammar) didefinisikan sebagai 4 tupel :

G = (V_n, V_t, S, Q)

V_n dan V_t adalah simbol Non Terminal dan Simbol Terminal.

S adalah sebuah elemen anggota V_n yang disebut Simbol Start.

Q merupakan himpunan Produksi.

Chomsky mengelompokkan Grammar menjadi 4 kelompok :

1. Tipe nol : UnRestricted Grammar (Tata Bahasa Tidak Terbatasi)

Tata Bahasa UnRestricted yang tidak merupakan anggota dari klasifikasi lainnya ditandai dengan aturan produksi yang bagian sebelah kirinya lebih panjang dari bagian sebelah kanan. Aturan produksi yang mengandung simbol hampa (^) pasti merupakan Tata Bahasa UnRestricted dan tidak termasuk klasifikasi lainnya.

2 Tipe satu : Context Sensitive Grammar (Tata Bahasa Tergantung Konteks)

Tata bahasa ini terdiri dari produksi berbentuk :

a ® b dengan ½a½ <== ½b½

dimana a adalah string dan ½a½ adalah panjang string a demikian juga b adalah string dan ½b½ adalah panjang string b. String adalah merupakan deretan simbol baik terminal maupun non terminal.

Contoh :

G = ( {S, B, C}, {a, b, c}, S, Q )

Dimana Q terdiri dari produksi berikut :

1. S ® aSBC ½ abC

2. bB ® bb

3. BC ® bc

4. CB ® BC

5. CC ® cc

1. Tipe dua : Context Free Grammar ( Tata Bahasa Bebas konteks)

Tata bahasa ini terdiri dari produksi berbentuk :

a ® b dengan ½a½ <== ½b½

dimana a adalah anggota V_n sedangkan b adalah string. Berarti Context Free Grammar seluruh produksi ruas kirinya hanya terdiri dari satu simbol yaitu simbol non terminal.

Contoh :

G = ( {S, C}, {a, b}, S, Q )

Dimana Q terdiri dari produksi berikut :

1. S ® aSa

2. S ® aCa

3. C ® b

2. Tipe tiga : Regular Grammar

Tata bahasa ini terdiri dari produksi berbentuk :

a ® b dengan ½a½ <== ½b½

dimana a adalah anggota V_n dan b mempunyai bentuk aB atau a dengan a anggota V_t dan B anggota V_n.









Contoh :

G = ( {S, A, B, C}, {a, b}, S, Q )

Dimana Q terdiri dari produksi berikut :

1. S ® aS ½ aB

2. B ® bC

3. C ® aC

4. C ® a

Regular Grammar merupakan subset dari Context Free Grammar.

Context Free Grammar merupakan subset dari Context Sensitive Grammar.

Context Sensitive Grammar merupakan subset dari UnRestricted Grammar.

2. POHON DERIVASI

Pohon derivasi merupakan suatu untai terminal yang tersusun dalam bentuk tree yang merupakan suatu himpunan produksi dengan cara melakukan sederetan produksi menggunakan produksi yang ada.

Pohon derivasi ini dapat diterapkan pada suatu ekspresi string ataupun pada ekspresi aritmatika.

¨ Pohon derivasi pada ekspresi string

Rumus :

<kalimat > Þ <subyek> <predikat>

<subyek > Þ <sandang> <benda> <keadaan>

<predikat > Þ <kerja> <obyek>

<obyek> Þ <benda> <keadaan>

¨ Pohon derivasi pada ekspresi aritmatika

Ada beberapa ketentuan yang sering dipakai dalam suatu penyusunan pohon derivasi untuk ekspresi aritmatika

Rumus :

<ekspresi> Þ <ekspresi> <asop> <suku> ½ <suku>

<suku> Þ <suku> <mdop> <faktor> ½ <faktor>

<faktor> Þ ( <ekspresi> ) ½ operand

<asop> Þ + ½ -

<mdop> Þ * ½ div



Contoh : Si adik kecil menendang bola besar.

Bila disusun dalam suatu pohon derivasi maka ekspresi string berbentuk :



Bahasan :

di klik biar gede gambarnya

Contoh : ( x - y ) * 5

Bila disusun dalam suatu pohon derivasi maka ekspresi aritmatika berbentuk :

Bahasan :

Di klik biar gede gambarnya

1. ravimalekinth says:

   July 31, 2009 at 10:15 am (Edit)

   wah bahasa itu rumit ya ternyata hahaha…

   Apa rumus di atas berlaku untuk semua bahasa? atau bahasa indonesia pada umumnya?

   Saya sendiri belum paham..mungkin coba diperbanyak contoh-contohnya agar bisa dipahami kaum awam.
2. honeynuts says:

   July 31, 2009 at 12:28 pm (Edit)

   Jo salut uy, makasih ya…. :)
3. honeynuts says:

   July 31, 2009 at 1:42 pm (Edit)

   Jo pas gw lihat lagi ada beberapa hal yang lupa ttg RG, CFG, dan ekspresi arimatika
   ada penjelasan mendetail nggak? Thanks
4. Johan Firdaus says:

   August 1, 2009 at 12:02 am (Edit)

   @ravim: hehehe, saya juga dah rada rada lupa, jaman kuliah neh, tutorial dari dosen maen copas aja di sini, kali aja bermanfaat, soal contoh lainnya nanti dulu deh, kapan2x aja
   @honey nuts : dah lupa bos gw, jaman kul soalnya, nanti deh kalo gw dah refresh ingatqan gw bales lagi

   hehehe