01 · Finite State Automata
Definisikan DFA/NFA lewat teks terstruktur, jalankan string untuk melihat jejak transisi, dan konversikan NFA menjadi DFA ekuivalen (subset construction). Tersedia juga evaluator Moore & Mealy Machine.
Definisi Mesin
Format: states, alphabet, start, final, lalu blok transitions: berisi state,simbol,tujuan per baris. Gunakan e untuk ε, dan pisahkan beberapa tujuan dengan | untuk NFA.
Uji String
Diagram State
Tabel Transisi
Moore Machine
Format state: nama/output. Output dibaca setiap kali memasuki sebuah state.
Mealy Machine
Baris transisi: dari,simbol,tujuan,output. Output dihasilkan pada transisi, bukan state.
02 · Regular Expression
Tulis sebuah Regular Expression, konversikan menjadi NFA lewat konstruksi Thompson, uji kecocokan string, konversikan ke DFA, dan lihat grammar reguler (Tipe 3 / right-linear) yang setara.
Ekspresi Reguler
Operator didukung: | union, * Kleene star, + satu-atau-lebih, ? opsional, () grouping, dan penulisan berdampingan untuk konkatenasi. Contoh: (a|b)*abb
Uji String terhadap Pola
NFA hasil Konstruksi Thompson
Grammar Reguler (Tipe 3) yang Setara
Satu nonterminal per state NFA. Aturan produksi: <state> → simbol <tujuan>, dan <state> → ε jika state tersebut final.
03 · Pushdown Automata & CFG
Definisikan Context-Free Grammar, cari derivasi leftmost untuk sebuah string, lihat pohon penurunan secara grafis, dan ikuti jejak konfigurasi stack Pushdown Automaton standar hasil konstruksi dari CFG tersebut.
Definisi CFG
Satu baris per nonterminal: S -> a S b | ab. Gunakan eps untuk ε, dan <Nama> untuk nonterminal bernama lebih dari satu huruf.
Hasil
Langkah Derivasi Leftmost
Pohon Penurunan (Parse Tree)
Jejak Konfigurasi Pushdown Automaton
PDA standar hasil konstruksi dari CFG: satu state, penerimaan dengan stack kosong (empty-stack acceptance).
04 · Hierarki Chomsky & Chomsky Normal Form
Konversikan CFG sembarang menjadi Chomsky Normal Form melalui lima tahap standar: START, DEL (eliminasi ε), UNIT (eliminasi produksi unit), TERM (isolasi terminal), dan BIN (binarisasi).
Hierarki Chomsky
Tipe 0 — Unrestricted Grammar
Diterima oleh Turing Machine. Tidak ada batasan bentuk produksi.
Tipe 1 — Context-Sensitive Grammar
Diterima oleh Linear Bounded Automaton. Panjang ruas kanan ≥ ruas kiri.
Tipe 2 — Context-Free Grammar
Diterima oleh Pushdown Automaton. Ruas kiri satu nonterminal tunggal. CNF adalah bentuk normal dari kelas ini.
Tipe 3 — Regular Grammar
Diterima oleh Finite State Automaton. Produksi berbentuk A → aB atau A → a (right-linear).
Definisi CFG
Contoh sudah tersedia. Gunakan eps untuk ε.