1. Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima
(accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.
Automata berasal dari bahasa Yunani automatos, yang berarti sesuatu yang bekerja
secara otomatis (mesin).
Pengertian mesin bukan hanya mesin elektronis/mekanis saja melainkan segala
sesuatu (termasuk perangkat lunak) yang memenuhi ketiga ciri di atas. Penggunaan
automata pada perangkat lunak terutama pada pembuatan kompiler bahasa
pemrograman. Secara garis besar ada dua fungsi automata dalam hubungannya
dengan bahasa, yaitu :
• fungsi automata sebagai pengenal (RECOGNIZER) string-string dari suatu bahasa,
dalam hal ini bahasa sebagai masukan dari automata
• fungsi automata sebagai pembangkit (GENERATOR) string-string dari suatu bahasa,
dalam hal ini bahasa sebagai keluaran dari automata.
2. Penerapan ekspresi reguler
¨ Digunakan untuk memerinci unit-unit leksikal sebuah bahasa pemrograman
(token).
contoh ekspresi reguler ‘bilangan real positif’
(0+1+…+9)(0+1+…+9)*.(0+1+…+9) (0+1+…+9)*
contoh ekspresi reguler ‘bilangan bulat’
(‘+’ + ’-‘ + l) (0+1+…+9)(0+1+…+9)*
3. “Deterministik” à setiap input alphabet/simbol dari suatu state hanya akan bertransisi ke satu state
lain. Atau dengan kata lain deterministik tidak ambigu dalam menentukan next state.
Contoh Deterministik
a. Mesin Ganjil.
b. Dari q0, tidak ada kerancuan jika menerima input 1 (akan ke q1), dan sebagainya.
“Non-Deterministrik” à setiap input alphabet/simbol dari suatu state mungkin akan bertransisi ke lebih
dari satu state lain.
Contoh Non-Deterministik
Lihat bahwa dari q0, akan muncul kerancuan jika menerima input 0 (akan ke q0 atau q1).
4. Finite Automata bekerja dengan cara mesin membaca memori masukan berupa tape yaitu 1 Karakter
tiap saat (dari kiri ke kanan) menggunakan head baca yang dikendalikan oleh kotak kendali state
berhingga dimana pada mesin terdapat sejumlah state berhingga.
Finite Automata selalu dalam kondisi yang disebut state awal (initial state) pada saat Finite Automata
mulai membaca tape. Perubahan state terjadi pada mesin ketika sebuah karakter berikutnya dibaca.
Ketika head telah sampai pada akhir tape dan kondisi yang ditemui adalah state akhir, maka string yang
terdapat pada tape dikatakan diterima Finite Automata (String-string merupakan milik bahasa bila
diterima Finite Automata bahasa tersebut).
5. Suatu string x dinyatakan diterima oleh bahasa NFA, M= (Q, _, d, S, F) bila {x | d
(S,x) memuat sebuah state di dalam F} Kedua finite automata di atas mampu
mengenali himpunan reguler secara presisi.
6. DFA dapat menuntun recognizer(pengenal) lebih cepat dibanding NDFA. Namun
demikian, DFA berukuran lebih besar dibanding NDFA yang ekivalen dengannya.
Lebih mudah membangun NDFA dibanding DFA untuk suatu bahasa, namun lebih
mudah mengimplementasikan DFA dibanding NDFA.
7. δ( q0,011)= δ( q2,11) =δ( q3,1)= q2 èDitolak
δ( q0,1010)= δ( q1,010) =δ( q3,10)=δ( q2,0)= q0 èDiterima
8. antara NFA ke DFA terdapat ekuivalensi.Dengan menggunakan tabel transisi kita
dapat lebih mudah menentukan ekuivalensi dari NFA ke DFA atau sebaliknya.
9. a. Kata/Word
b. Kalimat/Sentence
c. Frase/ Phrase
d. Anak kalimat/Clause
10. A. ?-move (? di sini bisa dianggap sebagai 'empty'),
jadi pada mesin nfa kita bisa mengubah state state tanpa harus bergantung pada suatu
inputan, cukup dengan menggunak e move, kita bisa menuju ke state state yg ada, dan
e move ini juga Disebut dengan transisi ? karena tidak bergantung pada suatu input
ketika melakukan transisi atau perpindahan. agar kita bisa mudah dalam
mengkombinasikan finite state automata.
B. e = Empty/kosong
closure = Himpunan state state
11. (a*| b)* = (a | b)*
Jawab :
(a|b)* = {ε, "a", "b", "aa", "ab", "ba", "bb", "aaa", ...}
Dengan diketahui a*= ε| a| aa| aaa| aaaa| …..,
Sedangkan b* = ε|b|bb|bbb|bbbb|…
Jadi(a|b)* yang merupakan gabungan concate dari a* dan b* maka
(a|b)* =(ε | a| b| aa| ab| ba| bb | aaa| ...)
Dengan diketahui: a*= ε| a| aa| aaa| aaaa| …..,
Maka(a*|b)* = (ε| a| aa| aaa| aaaa| …..|b)*
= (ε| a|b | aa|bb | aaa|bbb | aaaa| bbbb …..)
Maka terbukti, (a*|b)* = (a|b)*
12. Mesin Moore lebih aman digunakan, karena:
- Output berubah pada satu siklus.
- Pada Mesin Mealy, perubahan input dapat langsung merubah output, hal
dapat menyebabkan 2 mesin yang terhubung menjadi tidak sinkron.
- Mesin Mealy bereaksi lebih cepat pada input, karena:
- Bereaksi daam satu siklus
- Pada Mesin Moore, beberapa logika perlu diproses pada state untuk
menjadi output
menjadi output
13. Buatlah DFA yang ekuivalen dengan NFA disamping!
Pertama buatlah tabel transisinya
Kedua kita buat tupel dari tabel tersbut agar lebih detail
δ = {q0 , q1}
Ʃ = {0 , 1}
s = q0
f = q1
Lalu kita mulai membuat DFA nya
Dimulai dari state awal q0
State {q0} bila memperoleh input 0 menjadi state {q0, q1}.
State {q0} bila memperoleh input 1 menjadi state {q1}.
State {q1} memperoleh input 0 menjadi state ∅
State {q1} bila memperoleh input 1 menjadi state {q0, q1}.
Pada state {q0,q1} awalnya belum mempunyai busur dan pada DFA,sebuah state harus mempunyai busur sebanyak himpunan inputnya,karena itu kita tentukan terlebih dahulu arah busurnya dan busurnya ada 2.
δ({q0,q1},0) = {q0,0} ε {q1,0}
= {q0,q1} ε Ø
= {q0,q1}
δ({q0,q1},1) = {q0,1} ε {q1,1}
= {q1} ε {q0,q1}
= {q0,q1}
Jadi arah busur pada state {q0,q1} mengarah ke state itu sendiri.
Kemudian khusus pada state himpunan kosong (Ø) hanya menerima inputan dari statenya sendiri,jadi busur pada himpunan kosong mengarah ke state himpunan kosong.
 |
Ekivalensi Non-Deterministic Automata (NFA) ke Deterministic Finite Automata (DFA) |
Terakhir untuk menentukan final state pada DFA ini adalah dengan melihat NFA yang ekuivalen dengan DFA ini yaitu soal awal,
Kita ketahui Bahwa final state adalah q1,jadi pada DFA,final statenya adalah semua state yang ada hubungannya dengan q1 yaitu {q0,q1} dan {q1}
 |
Ekivalensi Non-Deterministic Automata (NFA) ke Deterministic Finite Automata (DFA) |
14 S → bA | aB A → bAA | aS | a B → aBB | bS | b
15. S → bA => S → P1A S → aB => S → P2B A → bAA =>A → P1AA => A → P1P3 A → aS => A → P2S B → aBB => B → P2BB => B → P2P4 B → bS => B → P1S
16. S -> ABaC | BaC | AaC | ABa | aC | Aa | Ba | a
A -> B | C | BC
B -> b
C -> D
D -> d
A -> B | C | BC
B -> b
C -> D
D -> d
0 Response to "JAWABAN SOAL TEORI BAHASA OTOMATA"
Post a Comment