Otomata
Arti menurut American Heritage Dictionary:
1. a robot
2. one that behaves
in an automatic or mechanical
fashion
Arti dalam dunia matematika
Berkaitan
dengan teori mesin abstrak, yaitu mesin sekuensial yang menerima input,
dan mengeluarkan output, dalam bentuk
diskrit.
Contoh :
¨ Mesin Jaja
/ vending machine
¨ Kunci
kombinasi
¨ Parser/compiler
Teori Otomata dan
bahasa formal, berkaitan dalam hal :
¨ Pembangkitan kalimat/generation : menghasilkan semua kalimat dalam bahasa L berdasarkan aturan yang dimilikinya
¨ Pengenalan kalimat / recognition : menentukan suatu string
(kalimat) termasuk sebagai salah satu
anggota himpunan L.
Bahasa Formal
Suatu
kalimat dibentuk dengan menerapkan serangkaian aturan produksi pada sebuah simbol ‘akar’. Proses penerapan aturan
produksi dapat digambarkan sebagai suatu
diagram pohon.
Teori dasar
Def. 1
sebuah string dengan panjang n yang dibentuk dari himpunan A adalah barisan dari n simbol
a 1a2...an ai Î A
Panjang string x dituliskan dengan |x|
Def 2.
String kosong (null string), dilambangkan dengan e adalah untaian
dengan panjang 0 dan tidak berisi
apapun. Panjang string x dituliskan dengan |x|
Def 3. dua
buah string a = a1a2...am dan b=b1b2...bn
dapat disambungkan menjadi string c
dengan panjang m+n sebagai berikut
c = a1a2...amb1b2...bn Operasi penyambungan tersebut dapat pula
diterapkan pada himpunan
Z=XY = {st | s ÎX Ù tÎY}
Def 4.
(Closure) . An adalah himpunan string dengan panjang n yang dibentuk
dari simbol-simbol di himpunan
simbol/alfabet A: Transitif
Closure/Kleen Closure adalah himpunan seluruh string yang dapat dibentuk
dari
A dengan berbagai panjang
A* = A0È A1È A2È A3È ...
Jika string kosong
dikeluarkan , akan diperoleh positive closure
A+ = A1È A2È A3È ...
Tata Bahasa
Aturan yang
disebutkan pada proses pengenalan dan pembangkitan kalimat.
Secara formal, tata
bahasa terdiri dari 4 komponen yaitu :
1. Himpunan berhingga, tidak kosong dari simbol-simbol non terminal T1
2. Himpunan berhingga, dari simbol-simbol non-terminal N
3. Simbol awal S Î N, yang merupakan salah satu anggota dari himpunan simbol
non-terminal.
4. Himpunan berhingga aturan produksi P yang setiap elemennya
dituliskan dalam
bentuk :
a ® b dimana a dan b adalah string yang
dibentuk dari himpunan T È N dan a harus berisi paling
sedikit satu simbol non-terminal.
Keempat komponen tersebut sering dituliskan sbb :
G = (T,N,S,P)
Bahasa
yang dihasilkan oleh G ditulis sebagai L(G), yaitu himpunan string yang
dapat diturunkan dari simbol awal S
dengan menerapkan aturan-aturan produksi yang terdapat pada P.
Aturan Produksi
Aturan
produksi a®b yang diterapkan
pada suatu string w=aac mengganti kemunculan. a menjadi b, sehingga string
tersebut berubah menjadi w=abc, sehingga dapat dituliskan
aac Þ abc (aac memproduksi abc).
Produksi tersebut dapat diterapkan berkali-kali
1 Þ w2 Þ w3 Þ ... Þ wn
atau dapat dituliskan
1 Þ* wn
jika minimal harus
ada 1 aturan produksi yang diterapkan :
1 Þ+ wn
Contoh 1
Tatabahasa G = {{S} ,
{a,b}, S , P } dengan aturan produksi P adalah
S
® aSb
S ® e
maka dapat dihasilkan suatu string
S
Þ aSb Þ aaSbb Þaabb sehingga dapat dituliskan
S Þ* aabb
Bahasa yang dihasilkan dari tatabahasa tersebut adalah
L(G) = { e , ab, aabb , aaabbb
, aaaabbbb, ... } atau dapat pula
dituliskan
L(G) = {anbn
| n ³ 0 }
Contoh 2
Tatabahasa G = {{S,A}
, {a,b}, S , P } dengan aturan produksi P adalah
S ® Ab
A
® aAb
A ® e
maka dapat dihasilkan suatu string
S
Þ Ab Þb
S
Þ Ab Þ aAbb Þ abb
S
Þ Ab Þ aAbb Þ aaAbbb Þ aabbb
Bahasa yang dihasilkan dari tatabahasa tersebut adalah
L(G) = { b , abb, aabbb ,
aaabbbb , aaaabbbbb, ... } atau dapat
pula dituliskan
L(G) = {anbn+1
| n ³ 0 }
Hirarki Bahasa
|
Kelas
|
Mesin pengenal
|
    Regular language
Context free
language
Context sensitive
language
Unrestricted language
|
Finite State
Automata
Push Down
Automata
Linear Bounded
Automata
Turing Machine
|
PERTEMUAN III
Finite State Automata (FSA)
¨ model matematika yang
dapat menerima input dan mengeluarkan output
¨ Memiliki
state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasar input dan fungsi
transisi
¨
Tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat
state terkini.
¨ Mekanisme
kerja dapat diaplikasikan pada : elevator, text editor, analisa leksikal, pencek parity.
|
FA
|
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
Contoh pencek parity
ganjil
Misal input :
1101
Genap 1 Ganjil 1 Genap 0 Genap 1 Ganjil diterima
mesin
Misal input : 1100
Genap 1 Ganjil 1 Genap 0 Genap 0 Genap ditolak
mesin
Def 1. Finite State Automata dinyatakan oleh 5 tuple
M=(Q , S , d , S , F )
Q = himpunan
state
S = himpunan simbol
input
d = fungsi
transisi d : Q ´ S S = state awal / initial state , S Î Q
F = state akhir, F Í Q
|
1
|
|
q1
|
|
1
|
|
Start q0 q0
|
|
0
0 0
|
|
0 0 0
|
|
q2 q3 q3
|
|
1
|
|
1
|
Contoh diatas,
Q = {Genap, Ganjil}
S = {0,1}
S = Genap
F = {Ganjil }
|
d
|
0
|
1
|
|
Genap
|
Genap
|
Ganjil
|
|
Ganjil
|
Ganjil
|
Genap
|
atau
d(Genap,0) =
Genap
d(Genap,1) =
Ganjil
d(Ganjil,0) =
Ganjil
d(Ganjil,1) =
Genap
Jenis FSA
|
d
|
0
|
1
|
|
Genap
|
Genap
|
Ganjil
|
|
Ganjil
|
Ganjil
|
Genap
|
atau
d(Genap,0) =
Genap
d(Genap,1) =
Ganjil
d(Ganjil,0) =
Ganjil
d(Ganjil,1) =
Genap
Jenis FSA
Deterministic
Finite Automata (DFA) : dari suatu state ada tepat satu state berikutnya untuk
setiap simbol masukan yang diterima
Non-deterministic Finite Automata (NFA) : dari suatu state ada 0, 1 atau lebih state berikutnya untuk setiap simbol masukan yang
diterima Deterministic Finite Automata
¨ Contoh :
pengujian parity ganjil.
¨ Contoh lain : Pengujian untuk menerima bit string dengan banyaknya
0 genap, serta banyaknya 1 genap.
¨ 0011 :
diterima.
¨ 10010 :
ditolak, karena banyaknya 0 ganjil
¨ Diagram
transisi-nya :
¨ DFA nya
Q = {q0 , q1 , q2
, q3 }
S = {0,1}
S = q0
F = { q0} fungsi transisi
|
d
|
0
|
1
|
|
q0
|
q2
|
q1
|
|
q1
|
q3
|
q0
|
|
q2
|
q0
|
q3
|
|
q3
|
q1
|
q2
|
d( q0,011)= d( q2,11) =d( q3,1)= q2
Ditolak
d( q0,1010)= d( q1,010) =d( q3,10)=d( q2,0)= q0
Diterima
Contoh DFA
lainnya :
Hi. I’m Designer of Blog Magic. I’m CEO/Founder of ThemeXpose. I’m Creative Art Director, Web Designer, UI/UX Designer, Interaction Designer, Industrial Designer, Web Developer, Business Enthusiast, StartUp Enthusiast, Speaker, Writer and Photographer. Inspired to make things looks better.
0 komentar:
Posting Komentar