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