Bahasa automata

1. Tupple : M = (Q, Ʃ, δ, S, F) Q = (q0, q1, q2, q3) Ʃ = (0, 1) Fungsi transisi δ (q0,0) = q1 δ (q0,1) = q0 δ (q1,0) = q2 δ (q1,1) = q0 δ (q2,0) = q3 δ (q2,1) = q0 δ (q3,0) = q3 δ (q3,1) = q3 TABEL FUNGSI TRANSISI δ 0 1 q0 q1 q0 q1 q2 q0 q2 q3 q0 q3 q3 q3 S = (q0) F = {q3} Diterima 0 0 0 (q0, 0) = q1 (q1, 0) = q2 (q2, 0) = q3 Diterima mesin DFA karna berhenti di state penerima / state akhir 1 0 0 0 (q0, 1) = q0 (q0, 0) = q1 (q1, 0) = q2 (q2, 0) = q3 Diterima mesin DFA karna berhenti di state penerima / state akhir 1 0 0 0 1 (q0, 1) = q0 (q0, 0) = q1 (q1, 0) = q2 (q2, 0) = q3 (q3, 1) = q3 Diterima mesin DFA karna berhenti di state penerima / state akhir Ditolak 1 0 1 0 (q0, 1) = q0 (q0, 0) = q1 (q1, 1) = q0 (q0, 0) = q1 Ditolak mesin DFA karna tidak berhenti di state penerima / state akhir 0 1 0 1 (q0, 0) = q1 (q1, 1) = q0 (q0, 0) = q1 (q1, 1) = q0 Ditolak mesin DFA karna tidak berhenti di state penerima / state akhir 1 0 1 1 0 0 (q0, 1) = q0 (q0, 0) = q1 (q1, 1) = q0 (q0, 1) = q0 (q0, 0) = q1 (q1, 0) = q2 Ditolak mesin DFA karna tidak berhenti di state penerima / state akhir Dari diagram State tersebut, Mesin ini adalah Mesin DFA 2. FSA (NFA dan DFA) adalah jenis FSA biasa yng memiliki karakteristik logika mesin masing-masing. Untuk jenis NFA dan DFA tugasnya hanya menelusuri input dan memiliki 2 keadaan yaitu diterima atau ditolak. FSA Output adalah jenis mesin finite state automata yang memiliki hasil output jenis keluaran berupa tampilan di layar monitor atau melalui media cetakan lain. Prinsip kerjanya tidak hanya membaca input, namu dapat menghasilkan output. Contoh : mesin komputer, kalkulator. 3. DFA 0,1 0,1 1 1 0 1 0 0 (tuple) M = (Q,Ʃ,δ,S,F) 1). Q = (q0,q1,q2,q3,q4) 2). Ʃ = ( 0,1) 3). Fungsi transisi : δ (q0,0) = q0 δ (q0,1) = q1 δ (q1,0) = q0 δ (q1,1) = q2 δ (q2,0) = q3 δ (q2,1) = q2 δ (q3,0) = q0 δ(q3,1) = q4 δ (q4,0) = q4 δ(q4,1) = q4 4). Tabel Fungsi transisi Δ 0 1 q0 q0 q1 q1 q0 q2 q2 q3 q2 q3 q0 q4 q4 q4 q4 5). State awal S = (q0) 6).State Akhir F= {q4} Contoh : Yang diterima mesin DFA a. 11010 (q0,1) = q1 (q1,1) = q2 (q2,0) =q3 inputan 11010 diterima mesin DFA karena berhenti pada state akhir (q3,1) =q4 (q4,0) =q4 Contoh : Yang ditolak mesin DFA b. 00110 (q0,0)=q0 (q0,0)=q0 inputan 00110 ditolak mesin DFA karena tidak berhenti pada state akhir (q0,1)=q1 (q1,1)=q2 (q2,0)=q3 • Mesin NFA 0,1 0 0,1 0 0,1 1 1 a. Tupel M = (Q,Ʃ,δ,S,F) Q = (q0,q1,q2,q3,q4) Himpunan State δ = (q0,0) = {q0,q1} δ (q0,1) = {q0,q1} δ (q1,0) = Ø δ (q1,1) = q2 δ (q2,0) = q2 δ (q2,1) = q2 δ (q3,0) = q4 δ (q3,1) = Ø δ (q4,0) = q4 δ (q4,1) = q4 tabel transisi Δ 0 1 q0 {q0,q1} {q0,q1} q1 Ø q2 q2 q2 Qq2 q3 q4 Ø q4 q4 q4 Contoh analisis mesin yang di terima : a. 111 (q0,1) = q0 inputan 1 1 1 diterima oleh mesin NFA karena berehenti pada state awal (q0,1 )= q0 (q0,1 )= q0 Contoh analisis mesin yang ditolak : b. 1 0 (q0,1) = q0 inputan 1 0 ditolak mesin NFA karena tidak berhenti pada state akhir (q0,0) = q3 • Mesin FSA 0 1 1 0 1 0 Tuple  Q = (q0,q1,q2)  Ʃ = (0,1)  Δ = (0,1,2)  δ = (fungsi transisi) δ (q0,0) = q0 δ (q0,1) = q1 δ (q1,0) = q2 δ (q1,1) = q0 δ (q2,0) = q1 δ (q2,1) = q2  State awal S = (q0) λ (q0) = 0 λ (q1) = 1 λ (q2) = 2