IF-UTAMA 1

IF-UTAMA 1

Grammar

Pertemuan : 4Dosen Pembina :Danang Junaedi

IF-UTAMA 2

Definisi

• Bahasa adalah himpunan kata-kata atau kalimat yang telah disepakati, contoh :– {makan, tidur, bermain, belajar} ⊂ Bahasa Indonesia

– {shit, sheet, damn, kiss, smell} ⊂ Bahasa Inggris

– {konichiwa, kombanwa, arigato, hon, susumu} ⊂ BahasaJepang

– {qirdun, asamaun, samaun, adzab} ⊂ Bahasa Arab

• Tata Bahasa adalah– Himpunan dari aturan-aturan struktural yang didefinisikan

dan berlaku pada suatu kalimat yang dibentuk dalam suatubahasa [2]

– Cara mendeskripsikan bahasa [5]

IF-UTAMA 3

Definisi

• Tata Bahasa adalah (contd)– Kumpulan dari himpunan –himpunan variabel,

simbol – simbol terminal, simbol awal dan aturan-aturan produksi, dimana

• Simbol terminal : simbol yg tidak dapat diturunkan lagi(biasanya ditulis dalam huruf kecil)

• Aturan produksi : Menspesifikasikan bagaimana suatutata bahasa melakukan transformasi suatu string kebentuk lainnya.

• Simbol Non terminal (Variabel) : simbol yang masih

bisa diturunkan lagi (biasanya ditulis dalam hurufkapital)

IF-UTAMA 4

Dua sifat penting yang harus dipenuhi olehsuatu tata bahasa [2]

• Simbol terminal dan non terminal harus disjoint

(tidak memiliki elemen yang sama)

• Setiap aturan produksi harus memuat paling

sedikit satu simbol nonterminal pada anggota

bagian kiri.

IF-UTAMA 2

IF-UTAMA 5

Manfaat & Motivasi Tata Bahasa

• Motivasi � menjelaskan bahasa alami, contohbahasa alami

<kalimat> � <subyek> <predikat> <obyek>

<subyek> � <kata benda><predikat> � <kata kerja><obyek> � <kata benda><kata benda> � dosen, mahasiswa<kata kerja> � mengajar

kalimat atau bahasa alami yang dihasilkan salahsatunya adalah dosen mengajar mahasiswa

• Manfaat � mendeskripsikan aturan tata bahasasebuah bahasa pemrograman seperti C, Pascal dts.

IF-UTAMA 6

Bahasa Mesin Otomata Batasan aturan produksi

Regular / tipe 3 Finite State Automata

meliputi Deterministic

Finite Automata (DFA) &

Non Detereministik Finite

Automata (NFA)

• α adalah sebuah simbol

variabel

• β maksimal memiliki

sebuah simbol variabel

yang bila ada terletak

diposisi paling kanan

Bebas Konteks /

context free / tipe 2

Push Down Automata

(PDA)

α berupa sebuah simbol

variabel

Context Sensitive /

tipe 1

Linier Bounded Automata |α | ≤ |β|

Unrestricted / Phase

structure / Natural

languange / tipe 0

Mesin Turing Tidak ada batasan

Tahun 1959 ahli bahasa bernama Noam Chomsky melakukanpenggolongan tingkat bahasa (Hirarki Chomsky) :

IF-UTAMA 7

Definisi Formal Regular Grammar [3]

G = (Vn, Vt, S, P)

• Bahasa G di atas terdiri dari 4 tuple, yaitu : – Vn = simbol non terminal (variabel)– Vt = simbol terminal

– S = simbol awal ∈ Vn– P = himpunan aturan produksi

• Setiap aturan produksi berbentuk :A � B (dibaca A menghasilkan B atau A menurunkan B)– A = minimal mengandung 1 simbol non terminal– B = (Vt)* U Vn

• Kumpulan aturan produksi :

A → B1

A → B2

…..

A → Bk

Bisa ditulis menjadi A → B1|B2|….. |Bk|IF-UTAMA 8

Contoh 1 : Regular Grammar

• G = {{S,A,B},{a,b,ε},S,P}Dimana aturan produksi P adalah

S � aBS � bAS � ε

A � abaSB � babS

atau dapat disederhanakan menjadiS � aB | bA | εA � abaSB � babS Studi Kasus :

Mana yang termasuk alfabet

non terminal, alfabet terminal,

simbol awal, dan himpunan

aturan produksi dari bahasa

formal pada contoh ini ???

IF-UTAMA 3

IF-UTAMA 9

Definisi Formal Context Free Grammar [4]

G = (Vn, Vt, S, P)

• Bahasa G di atas terdiri dari 4 tuple, yaitu :

– Vn = simbol non terminal (variabel)

– Vt = simbol terminal

– S = simbol awal ∈ Vn

– P = himpunan aturan produksi

• Setiap aturan produksi berbentuk :

A � B (dibaca A menghasilkan B atau A menurunkan B)

– A = minimal mengandung 1 simbol non terminal

– B = (Vn U Vt)*

IF-UTAMA 10

*G

Context Free Languages (CFL) [1]

The language generated by a CFG G, denoted by L(G), is :

L(G) = {ω | ω ∈ T* and S ⇒ ω }

Therefore,

– every string consists solely of terminals, and

– every string can be derived from S

It is called a context free language (CFL).

Notice that:– We must start with the start symbol

– We can use any production any number of times.

– The final string can only contain terminals.

IF-UTAMA 11

Contoh 2 : Context Free Grammar

• G = {{S},{a,b},S,P}Dimana aturan produksi P adalah

S � aSbS � ab

atau dapat disederhanakan menjadiS � aSb | ab

• G = {{E},{E},E,P}Dimana aturan produksi P adalah

E � E + EE � E * EE � (E)E � id

atau dapat disederhanakan menjadiE � E+E | E*E | (E) | id

Studi Kasus :

Mana yang termasuk alfabet

non terminal, alfabet

terminal, simbol awal, dan

himpunan aturan produksi

dari bahasa formal pada

contoh ini ???

IF-UTAMA 12

Definisi Formal Context Sensitive Grammar

G = (Vn, Vt, S, P)

• Bahasa G di atas terdiri dari 4 tuple, yaitu : – Vn = simbol non terminal (variabel)– Vt = simbol terminal – S = simbol awal ∈ Vn– P = himpunan aturan produksi

• Setiap aturan produksi berbentuk :A � B (dibaca A menghasilkan B atau A menurunkan B)– A = minimal mengandung 1 simbol non terminal– B = (Vn U Vt)*, dimana panjang B ≥ A

• Contoh aturan produksi pada Context Sensitive GrammarS � aSS � abaSb � aSAb

IF-UTAMA 4

IF-UTAMA 13

Aturan Ekspresi Reguler ke Tata BahasaReguler Linier Kanan 4

1. Bacalah ER dari kiri ke kanan, tulis X �, X sebagai simbol awal.2. Jika yang terbaca adalah a, tuliskan a.

3. Jika yang terbaca a*, tuliskan simbol non terminal baru, misalnya Y, kemudian tuliskan ‘Y � aY |’.

4. Jika yang terbaca (a + b), tuliskan Y, kemudian tuliskan ‘Y � aZ | bZ |’ dan ‘Z �‘ . Y dan Z adalah simbol non terminal baru. Ruas kanan dari ‘Z � …’ ditentukan oleh hasil pembacaan ER berikutnya.

5. Jika yang terbaca (a + b)*, tuliskan simbol non terminal baru, misalnya Y, kemudian tuliskan ‘Y � aY | bY |’.

6. Tuliskan ε jika seluruh ER sudah habis terbaca. 7. Jika yang terbaca berbentuk (r + s), di mana r atau s berbentuk

a* atau (a + b)*, tuliskan RY | SY, kemudian tuliskan ‘Y � …‘, ‘R � …’, dan ‘S � …’. Ruas kanan dari aturan ‘Y � …’ ditentukan oleh hasil pembacaan ER berikutnya. Ruas kanan aturan ‘R �…’ dan ‘S � ..’ ditentukan dengan jalan menganggap ekspresi r dan s sebagai ekspresi terpisah.

IF-UTAMA 14

Contoh Ekspresi Reguler ke Tata Bahasa Reguler Linier Kanan 4

• ER = 001*0 – Menurut aturan 2, 00 menghasilkan X � 00.

– Menurut aturan 3, 1* menghasilkan X � 00Y, Y � 1Y |.

– Menurut aturan 2, 0 menghasilkan 0 sehingga Y � 1Y | 0

– Menurut aturan 6, tuliskan ε sehingga X � 00Y, Y � 1Y | 0.

– Jadi G = (Vn, Vt, S, P) ; Vn = {X, Y} ; Vt = {0, 1} ; S = X ;

P = { X � 00Y, Y� 1Y | 0 }.

• ER = 00(0 + 1)*0 – Menurut aturan 2, 00 menghasilkan X � 00.

– Menurut aturan 5, (0 + 1)* menghasilkan X � 00Y, Y � 0Y | 1Y |. Menurut aturan 2, 0 menghasilkan 0 sehingga Y � 0Y | 1Y | 0. Menurut aturan 6, tulis ε sehingga X � 00Y, Y � 0Y | 1Y | 0 ε.

– Jadi G = (Vn, Vt, S, P) ; Vn = {X, Y} ; Vt = {0, 1} ; S = X ;

P = { X � 00Y, Y � 0Y | 1Y | 0 }.

• ER = 0(0 + 1)0* – Aturan 2, 0 menghasilkan X � 0.

– Aturan 4, (0 + 1) menghasilkan ‘X � 0Y, Y � 0Z | 1Z, Z �’.

– Aturan 3, 0* menghasilkan ‘ A � 0A |’.

– Aturan 6, tulis ε.

– Dengan demikian aturan produksi yang dihasilkan adalah

X � 0Y, Y � 0Z | 1Z, Z � A, A � 0A | ε. Aturan produksi ini bisa disederhanakan menjadi X � 0Y, Y � 0Z | 1Z, Z � 0Z | ε

IF-UTAMA 15

Contoh Konversi dari Tata Bahasa Linier Kanan Reguler ke Ekspresi Reguler 4

1. Tuliskan ekspresi dari kiri ke kanan, mulai dari simbol awal.

2. Jika aturan produksi berbentuk X � a, tuliskan a.

3. Jika aturan produksi berbentuk X � a | b, tuliskan(a+b)

4. Jika aturan produksi berbentuk X � aX, tuliskan a*

5. Jika aturan produksi berbentuk X � aX | bX, tuliskan(a + b)*

6. Jika aturan produksi berbentuk X � aY, dan terdapataturan produksi berbentuk Y � …., tuliskan aY, kemudian Y diganti sesuai aturan 2 sampai 6.

7. Jika aturan produksi berbentuk X � aY | bZ, tuliskan(aY + bZ), Y dan Z harus diganti sesuai denganaturan 2 sampai 7.

IF-UTAMA 16

Contoh Konversi dari Tata Bahasa RegulerLinier Kanan ke Ekspresi Reguler 4

• G = (Vn, Vt, S, P) ; Vn = { X } ; Vt = {0, 1} ; S = X ;

P = { X � 0X | 1 }

– Menurut aturan 4, X � 0X mengharuskan menulis 0* sehingga ER sekarang berisi 0*.

– Menurut aturan 2, X � 1 mengharuskan menulis 1 sehingga ER sekarang berisi 0*1

• G = (Vn, Vt, S, P) ; Vn = { X,Y } ; Vt = {0, 1, 2} ; S = X ;

P = { X � 1Y, Y � 0Y | 1Y | 1 | 2 }

– Menurut aturan 6, X � 1Y mengharuskan menulis 1Y sehingga ER sekarang berisi 1Y. Sekarang kita pikirkan pengganti Y.

– Menurut aturan 5, Y � 0Y | 1Y mengharuskan menulis (0+1)*.

– Menurut aturan 3, Y � 1 | 2 mengharuskan menulis (1+2).

– Jadi Y pada ER 1Y harus diganti dengan (0+1)*(1+2) sehingga ER yang terbentuk sekarang adalah 1(0+1)*(1+2).

• G = (Vn, Vt, S, P) ; Vn = { X, Y, Z } ; Vt = {0, 1} ; S = X ;

P = { X � Y | Z, Y � 0Y | ε, Z � 1Z | ε }

– Menurut aturan 7, X � Y | Z mengharuskan menulis (Y + Z) sehingga ER sekarang berisi (Y + Z). Apakah pengganti Y dan Z ? Menurut aturan 4, Y � 0Y mengharuskan menulis 0*.

– Menurut aturan 2, Y � e mengharuskan menuliskan ε.

– Jadi Y pada ekspresi (Y + Z) diganti dengan 0* (e tidak perlu ditulis). Z �1Z | ε menghasilkan 1* sehingga Z pada (Y + Z) dapat diganti dengan 1*.

– Dengan demikian ER untuk G di atas adalah ( 0* + 1* )

4

IF-UTAMA 5

IF-UTAMA 17

1. Tulis Ekspresi Regular berdasarkan aturan produksi dari Context Free Grammar berikut ini :G = {{S,A,B,C,D},{0,1, ε}, S, P}Dimana P terdiri dari

S → BC B → AB | ε A → 011 | 1 C → DC | ε D → 012. Tulis Context Free Grammar berdasarkan bahasa berikut ini :

Gh = ({K, H, N, T, X}, {a, b, c, d, e, f, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, H,P) Dimana P terdiri dari

H � XX � KTX � NTT � KTT � NTT � ε

K � a | b | c | d | e | fN � 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Studi Kasus [1 & 4]

IF-UTAMA 18

Tulis Context Free Grammar berdasarkan bahasaberikut ini :

3. {0i1i+k0k | i, k ≥ 1}

4. {0i1j0k | i, j, k ≥ 0, j ≥ i+k}

5. (0 + 1)*1(0 + 1)*0

6. (01)*(0 + 11)(01)*0

Studi Kasus [1]

IF-UTAMA 19

Referensi

1. http://www.cse.cuhk.edu.hk/~csc3130/2. Swinglly Purba, “Otomata dan Bahasa

Formal”, Graha Ilmu,Yogyakarta, 20083. Firrar Utdirartatmo, “Teori Bahasa dan

Otomata”, Graha Ilmu, Yogyakarta, 20054. Roni Djuliawan, M.T., “Diktat & Handout

Kuliah Teori Bahasa & Otomata”, Teknik Informatika – Universitas Widyatama, 2003

5. http://idhaclassroom.com/download/Teknik-Otomasi-Bahasa-Kompilasi/Bahasa-Kompilasi.pdf