Otomata.lab — Capstone Teori Bahasa & Otomata

Modul 01

Finite State Automata

Definisikan DFA/NFA, uji penerimaan string dengan penelusuran state, dan konversi NFA → DFA melalui konstruksi subset. Dilengkapi mesin dengan keluaran (Moore/Mealy).

Definisi Mesin

Definisi (states / alphabet / start / final / transitions)

Format & contoh

Baris states:, alphabet:, start:, final: dipisah koma.
Bagian transitions: diikuti baris dari,simbol,tujuan.
Epsilon: gunakan e atau ε. NFA: cukup tulis beberapa baris transisi dari state & simbol yang sama, atau gabungkan tujuan dengan | (mis. q0,0,q0|q1).

Uji String

String input

Belum diuji

Diagram State

Moore / Mealy Machine

Tipe mesin Definisi (states / alphabet / start / transitions / outputs)

Format & contoh

Sama seperti FSA, tanpa final:. Tambahkan bagian outputs:.
Moore — per baris: state,output (output ditempel pada state).
Mealy — per baris: state,simbol,output (output ditempel pada transisi).

String input

Modul 02

Regular Expression

Regex dikonversi ke NFA lewat konstruksi Thompson, diuji terhadap string, dapat dikonversi ke DFA, dan diturunkan aturan produksi grammar reguler (right-linear) yang setara.

Pola Regular Expression

Pola (mendukung: literal, |, *, +, ?, ( )) String uji

Belum diuji

Alfabet berupa karakter tunggal (huruf/angka). Contoh lain: (0|1)*011, a+b?c*

Grammar Reguler Setara

Aturan produksi tipe-3 (right-linear) diturunkan langsung dari NFA hasil konstruksi Thompson.

Bangun NFA terlebih dahulu.

Diagram NFA / DFA

Modul 03

Pushdown Automata & Context-Free Grammar

Definisikan CFG, lalu simulasikan penerimaan string oleh PDA berbasis grammar tersebut. Tampilkan derivasi leftmost/rightmost beserta pohon penurunan secara grafis.

Context-Free Grammar

Produksi (satu baris per non-terminal, alternatif dipisah |)

Format & contoh

Simbol non-terminal ditulis huruf besar (mis. S, A); terminal huruf kecil/angka.
String ε bisa ditulis ε atau e. Untuk simbol multi-karakter pisahkan dengan spasi, mis. S -> NP VP.
Contoh: S -> a S b | ε

Start

String uji Mode derivasi

Belum diuji

Langkah Derivasi

Belum ada derivasi.

Pohon Penurunan (Parse Tree)

Modul 04

Hierarki Chomsky & Chomsky Normal Form

Konversi CFG sembarang ke CNF secara bertahap: eliminasi produksi-ε, eliminasi unit production, eliminasi simbol tak berguna, lalu binarisasi & isolasi terminal.

Grammar Input

Produksi

Start

Hierarki Chomsky

Tipe 0 — Unrestricted Tipe 1 — Context-Sensitive Tipe 2 — Context-Free Tipe 3 — Regular

Tahapan Konversi ke CNF

Klik "Konversi ke CNF" untuk melihat setiap langkah transformasi.