VIRLAB

Tugas PengantarTeknik Kompilasi ( PTK )

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

jawab : Otomata merupakan mesin abstrak yang dapat mengenali (recognize), menerima (accept) atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu . Sedangkan Finite Automata merupakan mesin abstrak yang terdiri dari Head Pembaca dan Kontak Kontrol Stata Hingga.

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

jawab : RE (Regular Expresion) adalah bahasa regular dapat dinyatakan sebagai ekspresi regular dengan menggunakan 3 operator : concate, alternate, dan closure.

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.

jawab : Grammar diatas terdiri dari produksi berbentuk :

α à β dengan │α│ ß│β│. Dimana α ialah string dan │α│ ialah panjang dari string α demikian juga β ialah string dan│β│ ialah panjang dari string β. String disini adalah merupakan deretan simbol baik terminal maupun non terminal.

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 )

Jawab :

· (x-y*2+z) div (x div z)

· a*(2*c-b)*2

· **(y-5) * (y div 4+*)

<suku> <mdop> <faktor>

<ekspresi>

<suku> <mdop> <faktor>

<faktor> * <ekspresi> <ekspresi> <asop> <suku>

<ekspresi> <asop> <suku> <suku> <faktor>

<suku> <faktor> <suku> <mdop> <faktor>

<faktor > <faktor>

· (x*2*y)-((z+32) div y)

5. jawablah pertanyaan dibawah ini :

a. 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

b. Buatlah tabel transisi dari Deterministic Finite Automata berikut, dan tentukan apakah string berikut dapat diterima oleh Deterministic Finite Automata :

1101

0101

1001

Jawab :

a.

stata	0	1
q0	q2	q1
q1	q3	q0
q2	q0	q3
q3	q1	q2

b.

Penelusuran string 1101 : Penelusuran string

M(q0, 1101)=M(q1, 101) M(q0, 0101) =M(q2, 101)

=M(q0, 01) =M(q3, 01)

=M(q2, 1) =M(q1, 1)

=M(q3, ^) =M(q0, ^)

=q3(ditolak) =q0(diterima)

Penelusuran string 1001 :

M(q0, 1001) =M(q1, 001)

=M(q3, 01)

=M(q1, 1)

=M(q0, ^)

=q0(diterima)