Pertemuan ke-2Klasifikasi Chomsky

Otomata & Teori Bahasa FormalHanny Hikmayanti M.Kom

• Tata Bahasa/Grammar adalah sebagai kumpulan dari himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi.

• Aturan produksi merupakan pusat dari grammar yang menspesifikasikan bagaimana suatu tata bahasa melakukan transformasi suatu string atau karakter ke bentuk lainnya.

• Semua aturan produksi dinyatakan dalam bentuk “ α β “ (bisa dibaca α menghasilkan β, atau dibaca α menurunkan β)

• α merupakan simbol-simbol pada ruas kiri aturan produksi, sedangkan β merupakan simbol-simbol ruas kanan aturan produksi

• Simbol-simbol tersebut dapat berupa simbol terminal (Vt) dan simbol NON-Terminal (Vn)/Variabel.

• Simbol Vn adalah simbol yang masih dapat diturunkan, biasanya identik dengan huruf besar (‘A’,’B’,’C’)

• Simbol Vt adalah simbol yang sudah tidak dapat diturunkan lagi, biasanya identik dengan huruf kecil (‘a’,’b’,’c’)

• Dengan menerapkan aturan produksi, suatu tata bahasa bisa menghasilkan sejumlah string.

• Contoh aturan produksi :

E T | T+E | T * ET a

• Dari aturan produksi di atas, menghasilkan suatu variabel a atau variabel ekspresi a+a atau a*a

• E TT a

• E T+EE a+TE a+a

• E T*EE a*TE a*a

Tata Bahasa dan Klasifikasi Chomsky

Tata bahasa/Grammar G didefinisikan sebagai pasangan 4 tuple : VT , VN , S, dan Q, dan dituliskan sebagai G(VT , VN , S, Q), dimana :

VT : himpunan simbol-simbol terminal (atau himpunan token-token, atau alfabet)

VN : himpunan simbol-simbol non terminal

S Є VN : simbol awal (atau simbol start)

Q : himpunan produksi

Hierarki Chomsky

Bahasa Mesin Otomata Batasan Aturan Produksi

Reguler/Tipe 3 Finite State Automata (FSA) meliputi Deterministic Finite Automata (DFA), & Non-deterministic Finite Automata (NFA).

α adalah sebuah simbol variabelß maks memiliki sebuah simbol variabel yg bila ada terletak di posisi paling kanan

Bebas Konteks/Context Free/ Tipe 2

Push Down Automata (PDA)

α berupa sebuah simbol variabel

Context Sensitive/ Tipe 1

Linier Bounded Automata

|α| ≤ |ß|

Unresticted/ Phase Structure/ Natural Language/ Tipe 0

Mesin Turing Tidak ada batasan

Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (α → β), Noam

Chomsky mengklasifikasikan 4 tipe tata bahasa : • Tata bahasa tipe ke-0 : Unrestricted Grammar

(UG)

Ciri : α, β Є (VT | VN )*, |α|> 0 atau |α|> |β|• Tata Bahasa tipe ke-1 : Context Sensitive

Grammar (CSG)

Ciri : α, β Є (VT | VN )*, 0 < |α| ≤ |β|

• Tata Bahasa tipe ke-2 : Context Free Grammar (CFG)

Ciri : α Є VN , β Є (VT | VN )*

• Tata Bahasa tipe ke-3 : Regular Grammar (RG)

Ciri : α Є VN , β Є {VT , VT VN } atau α Є VN , β Є {VT , VN VT }

Contoh Analisa Penentuan Type Tata Bahasa

• Grammar G1 dengan Q1 = {S → aB, B → bB, B → b}. Ruas kiri semua

produksinya terdiri dari sebuah VN maka G1 kemungkinan tipe CFG atau RG.

Selanjutnya karena semua ruas kanannya terdiri dari sebuah VT atau string

VT VN maka G1 adalah RG

• Grammar G2 dengan Q2 = {S → Ba, B → Bb, B → b}. Ruas kiri semua

produksinya terdiri dari sebuah VN maka G2 kemungkinan tipe CFG atau RG.

Selanjutnya karena semua ruas kanannya terdiri dari sebuah VT atau string

VN VT maka G2 adalah RG

• Grammar G3 dengan Q3 = {S → Ba, B → bB, B → b}. Ruas kiri semua

produksinya terdiri dari sebuah VN maka G3 kemungkinan tipe CFG atau RG.

Selanjutnya karena ruas kanannya mengandung string VT VN (yaitu bB) dan juga string VN VT (Ba) maka G3 bukan RG, dengan kata lain G3 adalah CFG

• Grammar G4 dengan Q4 = {S → aAb, B → aB}. Ruas kiri semua produksinya

terdiri dari sebuah VN maka G4 kemungkinan tipe CFG atau RG. Selanjutnya karena ruas kanannya mengandung string yang panjangnya lebih dari 2 (yaitu aAb) maka G4 bukan RG, dengan kata lain G4 adalah CFG

• Grammar G5 dengan Q5 = {S → aA, S → aB, aAb → aBCb}. Ruas kirinya

mengandung string yang panjangnya lebih dari 1 (yaitu aAb) maka G5 kemungkinan tipe CSG atau UG. Selanjutnya karena semua ruas kirinya lebih pendek atau sama dengan ruas kananya maka G5 adalah CSG

• Grammar G6 dengan Q6 = {aS → ab, SAc → bc}. Ruas kirinya mengandung

string yang panjangnya lebih dari 1 maka G6 kemungkinan tipe CSG atau UG.

Selanjutnya karena terdapat ruas kirinya yang lebih panjang daripada ruas kananya (yaitu SAc) maka G6 adalah UG

Menentukan Grammar Sebuah Bahasa

• Tentukan sebuah grammar regular untuk bahasa L1 = { an | n ≥ 1}

• Jawab :

Q1 (L1 ) = {S → aS | a}S a atauS aS aa atauS aS aaS aaa

• Tentukan sebuah grammar bebas konteks untuk bahasa : L2 : himpunan bilangan bulat non negatif ganjil

• Jawab : Langkah kunci : digit terakhir bilangan harus ganjil. Buat dua buah himpunan bilangan terpisah : genap (G) dan ganjil (J) Q2 (L2 ) = {S → J|GS|JS, G → 0|2|4|6|8, J → 1|3|5|7|9}

• Tentukan sebuah gramar bebas konteks untuk bahasa :

L3 = himpunan semua identifier yang sah menurut bahasa pemrograman Pascal

dengan batasan : terdiri dari simbol huruf kecil dan angka, panjang identifier boleh lebih dari 8 karakter

• Jawab :

Langkah kunci : karakter pertama identifier harus huruf.

Buat dua buah himpunan bilangan terpisah : huruf (H) dan angka (A)

Q3 (L3 ) = {S → H|HT, T → AT|HT|H|A, H → a|b|c|…, A → 0|1|2|…}

• Contoh :

• G1 : VT = {I, Love, Miss, You}, V = {S,A,B,C}, P = {S ABC, A I, B Love | Miss, C You}

• S ABC

• I loveYou

• L(G1)={I love You, I Miss You}

• Tentukan apakah produksi-produksi berikut memenuhi aturan grammar Reguler :A bB bdBB CB bCB AdB bcdefA aSaA aSSAd dB

• Tentukan apakah produksi-produksi berikut memenuhi aturan Tata Bahasa Bebas Konteks :A aSaB AceB abB bcdefB bcdefGB aSSA BCDEFA AAAAAd dB

• Tentukan apakah produksi-produksi berikut memenuhi aturan grammar Konteks Sensitive :

A bcdefGB aSaB aSSB BCDEFAd dBad babC DEabcDef ghijklAB cdeAAA BBB

• Tentukan apakah produksi-produksi berikut memenuhi aturan grammar Unrestricted :

ad babC DEAB cdeABCDEFG hbA CDEFG