Deterministic Finite state Automata

Apa yang dimaksud dengan DFA?

• A. Model komputasi yang dapat mengenali pola dengan state dan transisi deterministik

• B. Algoritma untuk mengenkripsi data dalam sistem keamanan

• C. Struktur data yang digunakan untuk menyimpan informasi dalam array

• D. Model jaringan yang digunakan dalam komunikasi digital

Bagaimana DFA menentukan apakah suatu string diterima atau tidak?

• A. Dengan memeriksa apakah semua karakter string ada dalam alfabet yang digunakan

• B. Dengan mengevaluasi apakah string berakhir di state awal

• C. Dengan memproses string melalui state dan memastikan berakhir di state final

• D. Dengan mencocokkan string langsung dengan daftar pola yang sudah didefinisikan

3. Suatu DFA memiliki 4 state {q0, q1, q2, q3} dengan q0 sebagai state awal dan q3 sebagai state final. Jika DFA membaca string ‘110’, berikut adalah transisinya:

q0 → q1 (membaca ‘1’)

q1 → q2 (membaca ‘1’)

q2 → q3 (membaca ‘0’)

Ke state mana DFA berada setelah membaca string ‘110’?

:

• A. q0

• B. q1

• C. q2

• D. q3

Apa yang terjadi jika suatu DFA membaca string kosong (ε)?

• A. DFA langsung menerima string tersebut jika state awal adalah state final

• B. DFA otomatis menolak string kosong

• C. DFA akan langsung berpindah ke state final

• D. DFA akan membaca ulang string dari awal

(Sulit) – Suatu DFA dirancang untuk mengenali pola semua string yang berakhir dengan ‘01’. Jika DFA membaca string ‘110101’, apakah string ini diterima?

• A. Ya, karena string berakhir dengan ‘01’

• B. Tidak, karena DFA tidak bisa membaca string panjang

• C. Ya, karena semua string yang mengandung ‘01’ akan diterima

• D. Tidak, karena DFA hanya menerima string dengan panjang genap