Tugas VirLab

1. Jelaskan apa yang dimaksud dengan Otomata dan Finite Automata (otomata berhingga)!
Otomata adalah mesin abstrak yang menggunakan model matematika, tetapi matematika yang digunakan benar-benar berbeda dibanding matematika klasik dan kalkulus. Model yang digunakan adalah model mesin state (state machine model) atau model transisi state (state transition model).
Finite Automata (otomata berhingga) adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata dimana sistem dapat berada disalah satu dari sejumlah berhingga konfigurasi internal disebut state.
2. Jelaskan apa yang di maksud dengan Regular Expresion (RE) !
Reguler Expresion merupakan cara untuk mengecek atau memodifikasi text.
3. Diketahui Grammar, dengan himpunan 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.
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 )




A. (x - y * 2 + z ) div( x div z )


B. a * ( 2 * c – b ) * 2
<ekspresi>

<suku>

<suku> <mdop> <faktor>

<suku> <mdop> <faktor> * 2

<faktor> * ( <ekspresi> )

a <ekspresi> <asop> <suku>

<suku> - <faktor>

<suku> <mdop> <faktor> b

<faktor> * c

2
C. x * ( y – 5 ) * ( y div 4 + x )
<ekspresi>

<suku>

<suku> <mdop> <faktor>

<suku> <mdop> <faktor> * ( <ekspresi> )

<faktor> * ( <ekspresi> ) <suku>
X

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

<suku> - <faktor> <suku> <mdop> <faktor> + <faktor>

<faktor> 5 <faktor> div 4 x

y y
D. ( 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

Diagram transisi dari Deterministic Finite Automata :




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








tabel
0 1
q0 q2 q1
q1 q3 q0
q2 q0 q3
q3 q1 q2

a).m(q0,1101) => m(q1,101) => m(q0,01) => m(q2,1) => m(q3) Tracing berakhir di q3 (bukan stata penerima) => kalimat 1101 ditolak
b).m(q0,0101) => m(q2,101) => m(q3,01) => m(q1,1) => m(q0) Tracing berakhir di q0 (stata penerima) => kalimat 0101 diterima
c).m(q0,1001) => m(q1,001) => m(q3,01) => m(q1,1) => m(q0) Tracing berakhir di q0 (stata penerima) => kalimat 1001 diterima