PERTEMUAN 4 TEKNIK KOMPILASI

Perbedaan DFA dan NFA

·         Perbedaan DFA dan NFA, jika DFA state diberi input, selanjutnya tepat menuju 1 state, berbeda dengan NFA bisa saja menuju ke beberapa state selanjutnya.

·         Berbagai perbedaan DFA dan NFA lain, terkait ruang (space) dan eksekusi string yang dilakukan.

·          

Finite automata merupakan mesin automata dari bahasa reguler. Seperti yang kita ketahui, finite automata terbagi menjadi 2:

 

1.     Deterministic Finite Automata (DFA)

2.     Non-Deterministic Finite Automata (NFA)

Baik itu DFA maupun NFA, memiliki ciri-ciri atau karakteristik yang berbeda.

 

Deterministic Finite Automata (DFA)

Deterministic Finite Automata (DFA) menerima masukan (input) yang hanya memiliki 1 busur keluar.

DFA sendiri merupakan finite automata dengan memiliki 5 tuple yang direpresentasikan sebagai berikut:

·         Q, himpunan state, contohnya {q₀, q₁, q₂}

·         Σ, input alphabet, contohnya {a, b}

·         δ, fungsi transisi

·         q₀, state awal

·         F, state akhir

 

 

 

 

Contoh DFA

·         Q = {q₀, q₁, q₂}

·         ∑ = {0, 1}

·         q₀ = {q₀}

·         F = {q₂}

 Nondeterministic Finite Automata (NFA)

Nondeterministic Finite Automata (NFA) adalah salah satu bagian dari otomata berhingga atau Finite State Automata (FSA). Pada Nondeterministic Finite Automata (NFA) dimungkinkan satu simbol menimbulkan transisi ke lebih dari satu kondisi dan memberikan beberapa kemungkinan gerakan sehingga keluarannya tidak dapat dipastikan. Selain itu dimungkinkan juga terjadinya transisi spontan atau transisi –ε.

Nondeterministic Finite Automata (NFA) didefenisikan sebagai M yang merupakan sebuah koleksi dari 5 obyek (Q , Σ , s , F , ∆ ) dimana :

1. Q adalah sebuah himpunan hingga dari kedudukan-kedudukan.

2. Σ adalah sebuah abjad masukan.

3. s adalah salah satu kedudukan di dalam Q yang ditetapkan sebagai kedudukan permulaan.

4. F adalah sebuah koleksi dari kedudukan-kedudukan yang diterima atau final (koleksi / himpunan dari kondisi akhir).

5. ∆ adalah sebuah relasi pada (Q x Σ) x Q dan dinamakan relasi transisi.

(Kelley, 1995: 46).