TUGAS 3 (DFSA/DFA) DAN TUGAS 4 (TEORI BAHASA DAN OTOMATA)
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
