Modul 1
Finite State Automata (DFA & NFA)
Definisikan automaton Anda, uji sebuah string, dan lihat visualisasi serta jejak simulasinya secara langkah demi langkah.
Ringkasan Teori:
DFA (Deterministic Finite Automaton): untuk setiap state dan simbol, hanya ada TEPAT SATU transisi tujuan. Formal:
NFA (Non-deterministic Finite Automaton): dari satu state dengan satu simbol bisa ada 0, 1, atau lebih transisi tujuan, serta boleh memiliki epsilon-transition (transisi tanpa membaca simbol, ditulis sebagai
Setiap NFA dapat dikonversi menjadi DFA yang setara menggunakan algoritma Subset Construction.
DFA (Deterministic Finite Automaton): untuk setiap state dan simbol, hanya ada TEPAT SATU transisi tujuan. Formal:
M = (Q, Σ, δ, q0, F).NFA (Non-deterministic Finite Automaton): dari satu state dengan satu simbol bisa ada 0, 1, atau lebih transisi tujuan, serta boleh memiliki epsilon-transition (transisi tanpa membaca simbol, ditulis sebagai
"eps").
String pada NFA diterima jika ADA MINIMAL SATU jalur yang berakhir di accepting state.Setiap NFA dapat dikonversi menjadi DFA yang setara menggunakan algoritma Subset Construction.
Definisi Automaton
Gunakan format JSON di bawah ini untuk mendefinisikan automaton Anda, atau pilih salah satu contoh siap pakai.
Format:
states, alphabet, transitions,
start_state, accept_states. Gunakan "eps" untuk epsilon-transition pada NFA.
Visualisasi State Diagram
Jejak Simulasi (Trace)
Hasil Konversi NFA → DFA
Setiap state DFA merepresentasikan satu himpunan (subset) state NFA asli.
| State DFA | Himpunan State NFA Asal |
|---|
Definisi DFA Hasil Konversi (JSON)