UTS TBO 4A8

Langkah pertama dalam reduksi state pada DFA adalah:

• Mencari ε-closure

• Mengidentifikasi kombinasi state yang ada

• Menghapus state unreachable

• Membuat tabel transisi

Apa perbedaan utama NFA dan DFA?

• NFA selalu lebih besar dari DFA

• NFA bisa memiliki lebih dari satu transisi untuk satu simbol dari satu state

• DFA bisa memiliki ε-move

• DFA lebih sulit dikonversi ke ekspresi reguler

Sebuah NFA memiliki transisi dari state q0 ke q1 melalui ε. Apa arti transisi tersebut?

• Input harus ε

• Transisi terjadi tanpa memproses input

• Input harus kosong

• Transisi terjadi hanya jika tidak ada input lain

Bahasa dari ekspresi (ab)* adalah:

• Semua string yang mengandung 'ab'

• Semua string dengan jumlah a dan b sama

• Semua string yang merupakan pengulangan dari 'ab'

• Semua string yang diawali dengan 'a' dan diakhiri dengan 'b'

Diberikan NFA dengan transisi:

q0 --ε--> q1

q1 --a--> q2

q2 --b--> q3 (final)

Apakah string "ab" diterima?

• Ya

• Tidak

• Hanya jika a dan b muncul dua kali

• Hanya pada DFA

Sebuah DFA memiliki dua state: q0 (awal dan final) dan q1. Transisi:

q0 --a--> q1

q1 --a--> q0

Bahasa yang diterima oleh DFA ini adalah:

• Semua string dengan jumlah ‘a’ genap

• Semua string dengan jumlah ‘a’ ganjil

• Semua string yang dimulai dengan a

• Semua string kosong saja

Manakah dari ekspresi reguler berikut yang tidak valid?

• a* ( b U c )

• ( a b ) c*

• a U *b

• ( a U b)*

Ekspresi reguler ((a U b)* a) menerima string:

• bbaabb

• abab

• abba

• abbb

Apa arti simbol + dalam ekspresi reguler seperti a+?

• Nol atau lebih a

• Nol atau satu a

• Satu atau lebih a

• Hanya satu a

Jika ε-closure (q0) = {q0, q1, q2}, artinya...

• q0 langsung menuju q2 saja

• q0 hanya bisa ke q2 bila ada input

• q0 bisa mencapai q0, q1, dan q2 tanpa input

• q0 tidak bisa digunakan sebagai state awal