PERTEMUAN 4 TEORI BAHASA DAN OTOMATA [TBO]
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
DFA [Deterministic Finite Automata]
Semua FA yang telah kita lihat sampai sekarang adalah DFA Pada Deterministic Finite Automata, dari satu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima Apapun state saat itu (current state) atau masukan/input nya, selalu terdapat satu dan hanya satu state berikutnya
Catatan Penting !! δ(q, a) unik; setiap state q memiliki satu (dan hanya satu) transisi keluar untuk setiap simbol a ∈ Σ
Untuk setiap string input tertentu w, eksekusi benarbenar dapat diprediksi dan dapat diulangi. Oleh karena itu hasil dari eksekusi yang sama mesti sama. Sifat ini disebut dengan determinisme
Catt: δ Greek lowercase Delta; Σ Greek uppercase Sigma
Contoh DFA a
x
y
a
b
b z
a
b
State Start x y Final z
a y x z
b z z z
NFA
Non-Deterministic Finite Automata
Pada Non-Deterministic Finite Automata, dari suatu state bisa terdapat 0, 1 atau lebih busur keluar (transisi) berlabel simbol input yang sama Pada setiap pasangan state-input, dapat memiliki 0 (nol) atau lebih pilihan untuk state berikutnya
NFA Lanjt.. δ(q, a) adalah himpunan state-state:
bisa jadi himpunan kosong, atau lebih dari satu state
Dengan demikian, q bisa memiliki beberapa (atau tidak ada sama sekali) transisi keluar untuk setiap a ∈ Σ NFA dapat “menebak” langkah yang tepat, tanpa harus ditentukan (di dalam struktur NFA itu) terlebih dahulu. Tebakan ini muncul karena adanya beberapa pilihan. Sifat ini disebut dengan non-determinisme.
Contoh 1 : NFA L = {w ∈ {0, 1}*| w berakhir dengan 01}
Ide: Di suatu state NFA “menebak” bahwa akhir dari input sudah akan dimulai dan oleh karena itu NFA kemudian menunggu 01, dengan menggunakan non-determinisme.
Contoh 2 : NFA
a a, b
x
a
y
State Start x Final y
a {x,y}
b {y}
{y}
Ø
Non-deterministic FA [NFA]
Menerima: jika terdapat paling sedikit satu path yang berakhir di state Final di pohon trace eksekusi Menolak: jika semua path yang mungkin “terhenti” (stuck, halt) atau berakhir di state yang bukan Final Interpretasi: NFA selalu mengambil pilihan yang benar untuk memastikan penerimaan (asumsi: path yang berakhir di state Final memang ada) NFA membuat copy dirinya sendiri untuk menelusuri semua path yang mungkin NFA menjelajahi semua path secara parallel.
PENTING!
Semua NFA dengan bahasa L harus memastikan: ∀x L : semua path yang mungkin di pohon trace eksekusi menolak ∀x L : paling sedikit satu path di pohon trace eksekusi menerima
Meskipun NFA bebas “menebak”, NFA harus memastikan bahwa salah satu dari tebakannya benar. Caranya adalah dengan menebak semua tebakan yang mungkin.
Secara Formal
NFA N = (Q,Σ,δ,q0,F) memiliki struktur yang sama dengan DFA kecuali untuk fungsi transisi δ Q
δ:Q×Σ→2 ⇒ δ(q, a) adalah himpunan bagian dari Q.
Catt. Q Ingat : 2 adalah powerset dari Q
Contoh 3 : Penggabungan 2 FA
Berikut diperlihatkan sebuah NFA yang merupakan gabungan dari 2 buah FA, yaitu dengan cara menumpuk start state Dua FA berikut ini (FA1 dan FA2) masing-masing menerima language yang didefinisikan oleh regular expression r1 dan r2
Contoh 3 : Penggabungan 2 FA Lanjt.. a a
a
+ a
b
b b
a
b
a
b
a a, b
b
b
a, b
Contoh Penggabungan 2 FA Lanjt..
NFA yang akan dibuat untuk bisa mendefinisikan kedua language yang diterima oleh masing-masing FA terlihat seperti berikut ini: a a
a b a, b
a
a
+
b
a
b
b
a
b
b a, b b
Contoh 4
Perbedaan dengan NFA: fungsi transisi dapat memiliki 0 atau lebih fungsi transisi G = ({q0,q1,q2,q3,q4}, {0,1}, δ, q0, {q2, q4}}
δ q0 q1 q2 q3 q4
0 { q0,q3} ε {q2} {q4} {q4}
1 {q0,q1} {q2} {q2} ε {q4}
Contoh 4 Lanjt..
String diterima NFA bila terdapat suatu urutan transisi berdasar input, dari state awal ke state akhir. harus mencoba semua kemungkinan. Contoh : string 01001
Contoh 4 : string 01001
