POKOK BAHASAN MINGGU I

TATA BAHASA (GRAMMAR) dan POHON DERIVASI

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 = (Vn, Vt, S, Q)

Vn dan Vt adalah simbol Non Terminal dan Simbol Terminal.

S adalah sebuah elemen anggota Vn 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 :

dengan

dimana adalah string dan adalah panjang string demikian juga adalah string

dan adalah panjang string . 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 :

dengan

dimana adalah anggota Vn sedangkan 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 :

dengan

dimana adalah anggota Vn dan mempunyai bentuk aB atau a dengan a anggota Vt dan

B anggota Vn.

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 :

<kalimat>

<subyek> <predikat>

<sandang> <benda> <keadaan> <kerja> <obyek>

Si adik kecil menendang <benda>

<keadaan>

bola besar

Contoh : ( x – y ) * 5

Bila disusun dalam suatu pohon derivasi maka ekspresi aritmatika berbentuk :

Bahasan :

<ekspresi>

<suku>

<suku> <mdop> <faktor>

<faktor> * 5

<faktor>

( <ekspresi> )

<ekspresi> <adop> <suku>

<suku> + <faktor>

<faktor> y

x

POKOK BAHASAN MINGGU II

MESIN TURING

Mesin Turing M atas alfabet terdiri atas :

1. Tape atau Pita yang terbentuk dari deretan sel. Tape mempunyai sel terkiri, tetapi

mempunyai tak hingga sel kanan. Setiap sel hanya bisa berisi satu simbol pita.

Simbol pita terdiri dari huruf dalam alfabet T, huruf pada alfabet V ( alfabet tambahan), serta simbol blank.

2. Tape Head atau Kepala Pita yang bergerak mengamati satu sel tape pada suatu

waktu. Head dapat bergerak. Pada setiap gerak, head mencetak sebuah simbol pada

sel yang diamati, menghaps apa yang telah tertulis sebelumnya pada sel itu, lalu

bergerak ke kiri atau ke kanan.

3. Sebuah program, merupakan digraph hingga. Ia merupakan sebuah finite control.

Simpul digraph merupakan Stata. Selalu terdapat Stata Awal yang disebut START

dan sebuah himpunan Stata Akhir (boleh hampa) yang disebut HALT.

Setiap arkus digraph berbentuk :

i j

Di sini a serta b dalam T V {blank} adalah simbol tape. Sedangkan arah dalam {L,

R}. Ini berarti : jika selama komputasi kita ada di Stata I, head mengamati simbol a, maka

kita menuju simbol j, sementara mencetak simbol b, kemudian bergerak satu sel ke kiri

atau ke kanan, tergantung apakah Arah = L (kiri) atau R (kanan).

Mula-mula string input w, ditempatkan di bagian paling kiri dari tape, sisa di bagian

kanan diisi simbol blank. Tape head menunuk pada sel paling kiri. Program bermula pada

Stata Start. Kalau tercapai Stata Halt, komputasi dihentikan, untai diterima mesin turing.

Apabila sampai pada simpul I terjadi situasi sebagai berikut :

(a, b, ARAH)

Sedangkan simbol yang diamati bukan salah satu dari a1, a2, ….., an maka tidak ada

jalan untuk melanjutkan proses. Jika hal tersebut terjadi, maka proses dihentikan dan

string w ditolak oleh mesin.

Kasus lain penolakan w adalah pada saat tape head mengamati sel paling kiri,

ia diisntruksikan untuk bergerak ke kiri.

Contoh berikut adalah Mesin Turing atas alfabet T = {a, b} :

Mesin Turing dalam bentuk graf di atas dapat juga disajikan dalam bentuk diagram next state sebagai berikut :

1 2 3 4 5 6

a A, 2, R A, 2, R A, 4, L A, 4, L xxxxx Xxxxx

b

A

xxxxx

xxxxx

B, 3, L

xxxxx

xxxxx

A, 5, R

xxxxx

A, 1, R

xxxxx

xxxxx

xxxxx

xxxxx

B xxxxx B, 2, R B, 3, L xxxxx B, 5, R xxxxx

^ ^, 6, R xxxxx xxxxx xxxxx ^, 6, R xxxxx

Pada diagram next state tersebut, kolom menyatakan himpunan stata dari Mesin Turing,

sedangkan baris menyatakan himpunan string input dari Mesin Turing. Isi sel di tengah

berturut-turut menyatakan :

Simbol Output pada stata tersebut

Simbol Next State

Simbol Arah gerakan tape ( L = ke kiri, R = ke kanan ).

POKOK BAHASAN IIIAUTOMATA HINGGA DETERMINISTIK (AHD)

Dan

AUTOMATA HINGGA NON – DETERMINISTIK (AHN)

Automata Hingga merupakan mesin abstrak yang terdiri dari Head

Pembaca dan Kotak Kontrol Stata Hingga. Mesin ini membaca sebuah pita (tape), satu

persatu karakter, dari kiri ke kanan. Perubahan stata terjadi pada mesin jika suatu karakter

pita dibaca.

PITA

a a a b b b ^ … …

Read Head

Pada saat Automata Hingga mulai membaca Pita, ia harus selalu mulai dengan berada

pada suatu stata, yang ditunjuk sebagai stata awal. Sebuah Automata Hingga

Deterministik (AHD) terdiri atas 5 tupel (K, VT, f, q0, Z).

Dimana :

1. K adalah Himpunan Hingga berisi Stata.

2. VT adalah Himpunan Hingga berisi Simbol Input.

3. Sebuah fungsi f : K x VT, dimana K merupakan fungsi next-state.

4. q0 adalah Stata Awal anggota K.

5. Z adalah subset dari K yang berisi Stata Akhir atau Stata Penerima.

Contoh :

VT = (a,b) adalah himpunan simbol input.

K = (q0, q1, q2) adalah himpunan stata.

Z = (q0, q1) adalah himpunan stata penerima.

q0 adalah stata awal.

Fungsi Next-State f : K x VT K didefinisikan sebagai tabel berikut :

f a b

q0

q1

q2

q0 q1

q0 q2

q2 q2

Automata Hingga Deterministik dapat dinyatakan dalam diagram berupa Graph Berarah.

Pada graph berarah tersebut terdapat sebuah simpul sebagai stata awal q0. Lingkaran

berlapis dua digunakan untuk menyatakan stata penerima.

Bila f(q0, a) = q0, maka terdapat busur dari q0 ke q0 dengan label a.

Graph berarah dari Automata Hingga Deterministik di atas terlihat pada gambar berikut :

Automata M dikatakan dapat menerima atau mengenal string w jika Stata Akhir

merupakan Stata Penerima. Himpunan semua string yang dapat diterima oleh Automata

M dinotasikan dengan L (M).

Sebagai contoh, Automata M di atas dapat menerima untai :

aabababa

aaa

baab

serta menolak untai berikut :

bbaaaa

aababb

babbaa

Ada tiga tipe Automata Hingga, yaitu :

1. Automata Hingga Deterministik (AHD)

2. Automata Hingga Non-Deterministik (AHN)

3. Automata Hingga Non-Deterministik dengan transisi hampa

1. AUTOMATA HINGGA DETERMINISTIK (AHD)

AHD dapat dilengkapi dengan fungsi Next-State berikut :a) M(q, ^) = q untuk semua q anggota K

b) M(M(q, t), T), untuk semua t anggota VT dan T anggota VT

Dari definisi pertama, terlihat bahwa sebuah AHD tidak bisa mengubah stata tanpa

membaca sebuah karakter masukan. Definisi kedua adalah sebuah definisi yang bersifat

rekursif, yang menunjukkan di stata mana AHD berada pada saat di mulai di stata q

dengan mendapat input berupa string w = tT.

Sebuah string w adalah diterima oleh sebuah F = (K, VT, M, S, Z) jika M(S, W) = p,

sedemikian hingga w adalah anggota VT dan p anggota Z.

Atau dengan kata lain, string w diterima oleh AHD jika setelah membaca habis semua

karakter dari untai, AHD berada pada sebuah Stata Akhir. Himpunan semua untai w

anggota VT yang diterima oleh AHD F dinotasikan sebagai L(F).

Gambar berikut merupakan digraph Transisi dari sebuah AHD.

AHD pada contoh ini merupakan sebuah AHD yang menerima untai yang terdiri dari

simbol 0 dan 1. AHD tersebut dapat dinyatakan sebagai berikut :

F = ( {S, A, B, C}, {0, 1}, M, S, {S} ) dimana fungsi next state M adalah :

M(S, 0) = B M(S, 1) = A

M(A, 0) = C M(A, 1) = S

M(B, 0) = S M(B, 1) = C

M(C, 0) = A M(C, 1) = B

Fungsi stata berikut dari AHD kadang-kadang lebih mudah disajikan dalam bentuk tabel.

Untuk contoh di atas tabel yang terbentuk adalah :

STATA

INPUT0 1

SA

B

C

B A

C S

S C

A B

Contoh dari string yang diterima AHD di atas adalah 110101 dan contoh string yang

tidak dapat diterima adalah 11101. Bagan operasi AHD pada kedua untai di atas adalah

sebagai berikut :

Penelusuran string 110101 : Penelusuran string 11101 :

M(S, 110101) = M(A, 10101) M(S, 11101) = M(A, 1101)

= M(S, 0101) = M(S, 101)

= M(B, 101) = M(A, 01)

= M(C, 01) = M(C, 1)

= M(A, 1) = M(B, ^)

= M(S, ^) = B (ditolak)

= S (diterima)

2. AUTOMATA HINGGA NON-DETERMINISTIK (AHN)

AHN pada hakekatnya adalah sama seperti AHD, hanya saja pada AHN

dimungkinkan adanya transisi dari suatu stata ke lebih dari satu stata, untuk sebuah

karakter input yang sama. Sebagai contoh, AHN berikut menerima untai dalam bentuk

ambn, dimana m dan n bilangan bulat positif.

Sebuah untai akan diterima AHN, jika sedikitnya satu urutan transisi state berakhir pada

Stata Akhir. Untuk AHN di atas terlihat bahwa jika AHN menerima sebuah string, maka

penelusuran akan tetap di Stata A sampai dengan karakter a yang terakhir selesai dibaca.

AHN kemudian berubah mencapai stata B dan tetap pada stata B tersebut sampai karakter

b yang terakhir selesai dibaca. Selanjutnya terjadi transisi ke stata C.

AHN terdiri dari 5 tupel (K, VT, M, S, Z) dengan :

1. K adalah Himpunan Hingga Stata.

2. VT adalah Himpunan Simbol Input.

3. M adalah fungsi (pemetaan) next-state.

4. S adalah Stata Awal (anggota K).

5. Z adalah himpunan Stata Akhir (subset dari K).

Di sini fungsi next state dapat ditulis :

M(q, t) = {p1, p2, ….., pn}

Yang berarti bahwa pada saat pembacaan simbol input dapat terjadi transisi dari stata q

menjadi stata p1 atau p2 … atau pn. Sebagai contoh, sebuah AHN menerima untai yang

huruf awal dan huruf akhirnya sama. AHN tersebut dideskripsikan sebagai berikut :

F = ( {q0, q1, q2, q3, q4}, {a, b, c}, M, q0, {q0} )

Digraph AHN adalah sebagai berikut :

Tabel transisi yang ekuivalen dengan graph di atas adalah sebagai berikut :

INPUT

STATA a b c

q0q1

q2

q3

q4

{q0, q1} {q0, q2} {q0, q3}

{q1,q4} {q1} {q1}

{q2} {q2,q4} {q2}

{q3} {q3} {q3,q4}

^ ^ ^

Sebagai contoh, dengan input aca, nilai dari M(q0, aca) dapat ditentukan sebagai berikut :

Karena diketahui

M(q0, a) = {q0, q1}

Maka

M(q0, aca) = M(q0, ca) M(q1, ca)

Dan karena

M(q0, c) = {q0, q3}

M(q1, c) = {q1}

Maka

M(q0, ca) = M(q0, a) M(q3, a)

= {q1,q2} M(q3)

= {q0, q1, q3}

M(q1, ca) = M(q1, a) = {q1, q4}

Sehingga

M(q0, aca) = {q0,q1,q3} {q1,q4}

= {q0,q1,q3,q4}

dan karena stata yang tercapai memuat q4 yaitu stata akhir, maka untai aca diterima. Jadi, perbedaan antara AHD dan AHN adalah bahwa AHD banyaknya lintasan penelusuran untuk suatu untai adalah unik. Sementara pada AHN banyaknya lintasan mungkin lebih dari satu. Pada kenyataannya AHN dapat dikonversi menjadi AHD yang ekuivalen

Virtual Lab ATA 2008 – 2009

Tugas PengantarTeknik Kompilasi ( PTK )

1. Jelaskan apa yang dimaksud dengan Otomata dan Finite Automata (otomata

berhingga)!

2. Jelaskan apa yang di maksud dengan Regular Expresion (RE) !

3. Diketahui Grammar, dengan himpuinan simbol terminal { a, b} dan produksi sebagai

berikut ( huruf kecil menyatakan simbol terminal )

S a

S Sa

S b

S bS

Jelaskan bagaimana bentuk umum dari untai yang dibentuk oleh Grammar tersebut.

4. Buatlah pohon derivasi untuk ekspresi bentuk berikut :

( x – y * 2 + z ) div ( x div z )

a * ( 2 * c – b ) * 2

x * ( y – 5 ) * ( y div 4 + x )

( x * 2 * y ) – ( ( z + 32 ) div y )

5. Terdiri atas apa sajakah mesin turing, sebutkan dan jelaskan !

6. Diketahui Mesin Turing sebagai berikut :

Telusuri apakah untai berikut diterima atau ditolak :

a. ab b. aaabb c. abba

7. Gambarkan diagram transisi dari Deterministic Finite Automata berikut :

Q : {q0, q1, q2, q3}

∑ : {a, b}

S : q0

F : {q0, q1, q2}, dengan fungsi transisi dari DFA tersebut adalah :

Δ a b

q0 q0 q1

q1 q0 q2

q2 q0 q3

q3 q3 q4

8. Buatlah tabel transisi dari Deterministic Finite Automata berikut, dan tentukan

apakah string berikut dapat diterima oleh Deterministic Finite Automata :

a. 1101

b. 0101

c. 1001

9. Gambarlah diagram transisi untuk NFA berikut :

Q : {q0, q1, q2, q3, q4}

∑ : {0, 1}

S : q0

F : {q2, q4}, dengan fungsi transisi dari NFA tersebut adalah :

Δ 0 1

q0 {q0, q3} {q0, q1}

q1 Ø {q2}

q2 {q2} {q2}

q3 {q4} Ø

q4 {q4} {q4}

Start

1

q0

0

q3q2

q1

0

1

1

00

1

Apakah string berikut ini :

a. 001

b. 10010

c. 111000

Dapat diterima oleh Non-deterministik Finite Automata pada Diagram Transisi untuk

NFA diatas?

10. Diketahui bentuk AHD seperti terlihat pada gambar.

Tuliskan tupel dari AHD

Buatlah tabel dari AHD

Telusuri untai berikut apakah diterima atau ditolak :

aabbaba

baaaba

abbbaab

********* Selamat Mengerjakan **********

Keterangan :

1. Tugas Diatas dikumpulkan dalam bentuk print dan di jilid.

2. Tugas ini adalah tugas Peorangan bukan tugas kelompok

3. Bisa dikumpulkan perkelas atau perorangan ( Nanti akan

mendapatkan tanda / bukti mengumpulkan tugas )