Deterministic Finite Automata
Finite State Automata (FSA)adalah
model matematika yang dapat menerima input dan mengeluarkan output. FSA
Memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke
state lainnya berdasar input dan fungsi transisi. FSA Tidak memiliki
tempat penyimpanan/memory, hanya bisa mengingat state terkini. Mekanisme kerja
dapat diaplikasikan FSA pada : elevator, text editor, analisa leksikal, pencek
parity.
TUGAS 3
DFSA/DFA
(Tugas 1 Teori Bahasa & Otomata)
1.)
Buatlah tabel transisinya
2.) Bacalah
input
a =
abbabbaaa
b = bbbabbaa
c = ab
Jawaban
:
1.)
Tabel Transisi :
δ
a b
→ q0 q0,q2
q1
* q1
q1,q2 q2
q2
- q0,q1
2.) Baca
Inputnya menjadi :
a. Jika T diberi input abbabbaaa dengan State awal (q0, abbabbaaa), maka :
a. Jika T diberi input abbabbaaa dengan State awal (q0, abbabbaaa), maka :
q0,
abbabbaaa ┣ T
(q0, bbabbaaa)
┣ T (q1, babbaaa)
┣ T (q1, abbaaa)
┣ T (q2, bbaaa)
┣ T (q1,baaa)
┣ T (q1,aaa)
┣ T (q1,aa)
┣ T (q1,a)
┣ T (q1,e)
Karena
(q0, abbabbaaa) ┣ *
T jadi abbabbaaa diterima T
b. Jika
T diberi input bbbabbaa dengan State awal(q0, bbbabbaa), maka :
q0,
bbbabbaa ┣ T
(q1,bbabbaa)
┣ T (q1,babbaa)
┣ T (q1,abbaa)
┣ T (q2,bbaa)
┣ T
(q0,baa)
┣ T(q1,aa)
┣ T(q1,a)
┣ T (q1,e)
Karena
(q0,bbbabbaa) ┣ *
T jadi bbbabbaa diterima T
c. Jika
T diberi input ab dengan State awal (q0,ab), maka :
q0,
ab ┣ T
(q0,b)
┣ T (q1,e)
Karena
(q0,ab) ┣ *
T jadi AB diterima T
TUGAS 4
1.) Soal
:
Dari
diagram state di atas tentukan :
a. ABAAAAB
b. BBBBAAA
c. BABABAB
Jawaban
:
a.
ABAAAAB
b.
BBBBAAA
c.
BABABAB
sumber : https://fairuzelsaid.wordpress.com/2011/05/01/teori-bahasa-dan-otomata-finite-state-automata/
