Simulator Teori Bahasa & Otomata

Modul 1 — Finite State Automata

Simulator DFA & NFA dengan visualisasi diagram state. Input string & definisi mesin, lihat trace accepted/rejected lengkap. Bonus: Moore & Mealy Machine.

DFANFAMooreMealy

Modul 2 — Regular Expression

Input RE, konversi ke NFA/DFA, uji kecocokan string. Tampilkan grammar reguler setara dan aturan produksi.

RE→NFAPattern MatchGrammar Reguler

Modul 3 — PDA & CFG

Simulator PDA berbasis CFG. Input grammar dan string, tampilkan proses derivasi leftmost/rightmost dan parse tree grafis.

CFGDerivasiParse TreePDA

Modul 4 — Hierarki Chomsky & CNF

Konversi CFG ke Chomsky Normal Form (CNF) langkah demi langkah. Visualisasi hierarki Chomsky tipe 0–3.

Tipe 0–3CNFGNFEliminasi

Modul 1 — Finite State Automata

Simulator DFA, NFA, Moore Machine, dan Mealy Machine dengan visualisasi diagram transisi.

Definisi DFA

States (pisahkan koma) *

Alfabet Σ (pisahkan koma) *

State Awal *

State Final (pisahkan koma) *

Fungsi Transisi δ (satu per baris: state,input=next_state)

Contoh: mesin yang menerima string berisi paling tidak dua '1'

String Uji *

Hasil & Trace

Tekan "Jalankan DFA" untuk melihat hasil simulasi.

Diagram State

Diagram akan muncul setelah dijalankan

Tabel Transisi

Tabel muncul setelah dijalankan.

Definisi NFA

States

Alfabet Σ

State Awal

State Final

Transisi NFA (state,input=next1|next2, gunakan ε untuk epsilon)

Contoh: NFA menerima string berakhir "abb"

String Uji

Hasil NFA

Tekan "Jalankan NFA" untuk melihat hasil.

Subset Construction (NFA→DFA)

Konversi muncul setelah dijalankan.

Moore Machine

States

Alfabet Input

State Awal

Output per State (state=output)

Transisi (state,input=next)

String Input

Output Moore Machine

Tekan "Jalankan Moore" untuk melihat output per state.

Mealy Machine

States

Alfabet Input

State Awal

Transisi + Output (state,input=next,output)

Contoh: komplemen bit (XOR dengan bit sebelumnya)

String Input

Output Mealy Machine

Tekan "Jalankan Mealy" untuk melihat output per transisi.

🔤 Modul 2 — Regular Expression

Konversi Regular Expression ke NFA/DFA, uji kecocokan string, dan tampilkan grammar reguler setara.

Input Regular Expression

Regular Expression *

Operator: | (union), * (kleene star), + (satu atau lebih), ? (opsional), () (grup), . (concat)

String Uji

Masukkan RE dan string uji lalu tekan tombol.

Test Multiple String

Daftar String (satu per baris)

Grammar Reguler Setara

Grammar muncul setelah RE dijalankan.

Langkah Konstruksi NFA (Thompson)

Langkah konstruksi NFA muncul setelah dijalankan.

🌳 Modul 3 — Pushdown Automata & CFG

Simulator PDA berbasis CFG. Input grammar dan string, tampilkan derivasi dan parse tree grafis.

Context-Free Grammar

Start Symbol

Aturan Produksi (satu per baris: A -> α)

Contoh: L = {aⁿbⁿ | n≥1}. Gunakan ε untuk epsilon.

String Uji

Tipe Derivasi

Hasil Derivasi

Masukkan grammar dan string lalu tekan "Derivasi".

Parse Tree

Parse tree muncul setelah derivasi berhasil.

Pushdown Automata

States

State Awal

State Final

Bottom of Stack Symbol

Transisi (state,input,stack_top = next,push)
Gunakan ε untuk epsilon

PDA untuk L={aⁿbⁿ|n≥1}

String Input

Konfigurasi PDA

Tekan "Jalankan PDA" untuk melihat konfigurasi stack.

📐 Modul 4 — Hierarki Chomsky & CNF

Visualisasi hierarki Chomsky tipe 0–3 dan konversi CFG ke Chomsky Normal Form (CNF) langkah demi langkah.

Hierarki Chomsky — Klik layer untuk detail

Tipe 0 — Unrestricted Grammar (Recursively Enumerable)

Tipe 0 (Unrestricted Grammar)
Tidak ada batasan pada aturan produksi. Bentuk: α → β, di mana α dan β adalah string bebas.
⚙️ Dikenali oleh: Mesin Turing
📌 Contoh: L = {aⁿbⁿcⁿ | n≥1}

Tipe 1 — Context-Sensitive Grammar

Tipe 1 (Context-Sensitive Grammar)
Aturan: αAβ → αγβ, di mana |αAβ| ≤ |αγβ| (produksi tidak memperpendek).
⚙️ Dikenali oleh: Linear Bounded Automaton (LBA)
📌 Contoh: L = {aⁿbⁿcⁿ | n≥1}

Tipe 2 — Context-Free Grammar (CFG)

Tipe 2 (Context-Free Grammar)
Aturan: A → α, di mana A adalah satu non-terminal dan α bebas.
⚙️ Dikenali oleh: Pushdown Automaton (PDA)
📌 Contoh: L = {aⁿbⁿ | n≥1}, L = {ww^R | w ∈ {a,b}*}

Tipe 3 — Regular Grammar

Tipe 3 (Regular Grammar)
Aturan hanya boleh: A → aB (right-linear) atau A → Ba (left-linear).
⚙️ Dikenali oleh: Finite State Automaton (DFA/NFA)
📌 Contoh: L = {a*b+}, semua bahasa regular

ℹ️ Setiap bahasa Tipe 3 ⊂ Tipe 2 ⊂ Tipe 1 ⊂ Tipe 0. Hierarki ini bersifat proper inclusion.

Input CFG untuk Konversi CNF

Start Symbol

Aturan Produksi

Format: A -> α | β (atau satu per baris). Gunakan ε untuk epsilon.

Langkah-langkah Konversi CNF

Langkah-langkah CNF muncul setelah konversi.

Klasifikasi Grammar

Start Symbol

Aturan Produksi (satu per baris)

Masukkan grammar dan sistem akan mengklasifikasikan tipenya.

Hasil Klasifikasi

Klasifikasi muncul setelah dijalankan.