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/
Tidak ada komentar:
Posting Komentar