Minggu, 10 April 2011

Tugas PengantarTeknik Kompilasi ( PTK )

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










Oval: divv










Oval: (
Oval: )
Oval: (
Oval: )





Oval: +
Oval: divv
Oval: zOval: -






Oval: z
Oval: x


Oval: 2

Flowchart: Connector: *





Oval: x
Oval: y










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







Flowchart: Connector: *



Oval: )Oval: (
Flowchart: Connector: *Oval: 2



Oval: aOval: -

Flowchart: Connector: *

Oval: cOval: b

Oval: 2








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






Flowchart: Connector: )Flowchart: Connector: (
Flowchart: Connector: *






Flowchart: Connector: (
Flowchart: Connector: )


Flowchart: Connector: * *

Flowchart: Connector: +

Flowchart: Connector: *Flowchart: Connector: -

Oval: divvFlowchart: Connector: *

Flowchart: Connector: 4Flowchart: Connector: 5

Flowchart: Connector: yFlowchart: Connector: y





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





Oval: -





Oval: (
Oval: )








Oval: (
Oval: )




Oval: div ddivdiv








Oval: (

Flowchart: Connector: *

Oval: )



Oval: yFlowchart: Connector: *

Oval: y

Oval: +Oval: 2


Oval: x




Oval: 322


Oval: z







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)

Tidak ada komentar:

Posting Komentar