Preview Percuma
Lesson Practice
TEKNOLOGI
ADVANCED THEORY OF COMPUTING
Silibus & Latihan Preview
Pilih pelajaran, topik dan latihan mengikut susunan silibus.
Pelajaran
2
Finite Automata — 16 Oktober 2026 (Ganti 11 Oktober)
Tajuk
1
2.1 Deterministic Finite Automata (DFA)
Nota 2.1: Deterministic Finite Automata (DFA)
1. Apakah DFA?
DFA ialah mesin dengan bilangan state yang terhingga. Mesin membaca input satu simbol demi satu simbol untuk menentukan sama ada seluruh rentetan diterima atau ditolak.
Deterministic bermaksud: bagi setiap state dan setiap simbol dalam alphabet, terdapat tepat satu state destinasi. Oleh itu, satu input mempunyai satu laluan pemprosesan dari initial state.
DFA tidak menggunakan transisi λ. Setiap transisi membaca satu simbol input.
2. Definisi formal
M = (Q, Σ, δ, q₀, F)
Baca: “Mesin M ditakrifkan oleh Q, sigma, delta, q kosong dan F.”
• Q: set semua state. Bilangannya terhingga.
• Σ: input alphabet, iaitu set simbol input yang dibenarkan.
• δ: fungsi transisi yang menentukan state seterusnya.
• q₀: initial state; q₀ ialah ahli Q.
• F: set accepting states; F ialah subset Q.
Q besar ialah kumpulan semua state. q₀ ialah satu state tertentu dalam kumpulan itu.
3. Cara membaca graf
• Bulatan mewakili state.
• Anak panah dari luar menandakan initial state.
• Bulatan berganda menandakan accepting state.
• Anak panah antara state ialah transisi; labelnya ialah simbol yang dibaca.
• Gelung kembali kepada state yang sama bermaksud mesin kekal di situ selepas membaca simbol pada gelung.
• Label a,b bermaksud a atau b; setiap pergerakan tetap membaca satu simbol.
4. Fungsi transisi δ
δ : Q × Σ → Q
Baca: “Delta ialah fungsi daripada Q silang sigma kepada Q.” Tanda × membentuk pasangan state semasa dan satu simbol input. Hasilnya satu state destinasi.
δ(q₀, a) = q₁ dibaca: “Apabila berada di q kosong dan membaca a, pergi ke q satu.”
Dalam jadual transisi, baris ialah state semasa, lajur ialah simbol input dan isi petak ialah state destinasi.
5. Contoh mesin pengecam abba
Q = {q₀, q₁, q₂, q₃, q₄, q₅}; Σ = {a,b}; initial state = q₀; F = {q₄}.
Laluan yang menerima: q₀ —a→ q₁ —b→ q₂ —b→ q₃ —a→ q₄.
Transisi yang tidak mengikut urutan itu menuju ke q₅. Dari q₄, simbol tambahan a atau b juga menuju ke q₅. Di q₅, a atau b kembali ke q₅.
6. Trap state
Dalam contoh ini, q₅ ialah trap state yang bukan accepting state. Setelah masuk ke q₅, mesin tidak dapat keluar daripadanya. Baki input masih dibaca melalui gelung a,b, tetapi rentetan akhirnya ditolak.
q₅ hanyalah nama dalam contoh ini; nama state tidak menentukan fungsinya. Rujuk panah dan penandaan pada graf.
7. Memproses seluruh rentetan
δ* dibaca “delta bintang”. Ia melanjutkan δ untuk memproses seluruh rentetan, termasuk rentetan kosong.
δ*(q₀, abba) = q₄: bermula di q₀, baca a ke q₁, b ke q₂, b ke q₃ dan a ke q₄.
δ*(q₀, ab) = q₂: input habis di q₂, maka ditolak kerana q₂ bukan accepting state.
δ*(q₀, abbaa) = q₅: selepas abba mesin di q₄, tetapi masih ada satu a yang membawa mesin ke q₅. Maka ditolak.
δ*(q₀, λ) = q₀: rentetan kosong tidak menggunakan sebarang transisi. Contoh ini menolaknya kerana q₀ bukan accepting state.
8. Peraturan penerimaan
Habiskan seluruh input dahulu, kemudian semak state akhir. Rentetan diterima jika state akhir ialah ahli F. Melepasi accepting state sebelum input habis belum menjamin penerimaan.
Bagi mesin contoh ini, hanya rentetan tepat abba diterima: L(M) = {abba}. Mesin DFA lain boleh menerima bahasa yang berbeza.
Teruskan ke tajuk 2.2 Language Accepted by DFA untuk penerangan lanjut tentang δ*, walk dan notasi L(M). Gunakan simulator DFA untuk menguji input langkah demi langkah.
Pelajaran
3
Non-Deterministic Finite Automata — 18 Oktober 2026
Tajuk
1
3.1 Nondeterministic Finite Automata (NFA)
Nota 2.3: Nondeterministic Finite Automata (NFA)
1. Apakah NFA?
NFA ialah mesin dengan bilangan state yang terhingga. Mesin membaca rentetan input untuk menentukan sama ada rentetan itu diterima atau ditolak.
Nondeterministic bermaksud satu state dengan simbol input yang sama boleh mempunyai beberapa state destinasi. Ada juga pasangan state dan simbol yang langsung tiada transisi.
Semasa menelusuri input, kita mengambil kira semua kemungkinan laluan. Kita tidak memilih satu laluan sahaja lalu mengabaikan laluan lain.
2. Perbezaan asas DFA dan NFA
• DFA: setiap pasangan state dan simbol input mempunyai tepat satu state destinasi.
• NFA: setiap pasangan state dan simbol input boleh mempunyai sifar, satu atau beberapa state destinasi.
• DFA menghasilkan satu state selepas input diproses.
• NFA menghasilkan set semua state yang boleh dicapai selepas input diproses.
• NFA menerima input jika sekurang-kurangnya satu laluan menerima seluruh input.
NFA dan DFA mempunyai kuasa pengecaman bahasa yang sama: kedua-duanya mengenali bahasa regular. NFA boleh memberikan gambaran mesin yang lebih ringkas bagi sesetengah bahasa.
3. Definisi formal
M = (Q, Σ, δ, q₀, F)
Baca: “Mesin M ditakrifkan oleh Q, sigma, delta, q kosong dan F.”
• Q: set semua state yang terhingga.
• Σ: set simbol input.
• δ: fungsi transisi.
• q₀: initial state, iaitu satu ahli Q.
• F: set accepting states, iaitu subset Q.
Lima komponen ini sama namanya seperti DFA. Perbezaan utama ialah fungsi transisi NFA menghasilkan SET state.
4. Cara membaca fungsi transisi NFA
Bagi NFA tanpa transisi λ:
δ : Q × Σ → P(Q)
Baca: “Delta ialah fungsi daripada Q silang sigma kepada set kuasa Q.”
P(Q), juga ditulis 2^Q, ialah set semua subset Q. Oleh itu, hasil transisi boleh berupa set kosong, satu state dalam kurungan set, atau beberapa state.
Contohnya, jika Q = {q₀,q₁}, maka:
P(Q) = {∅, {q₀}, {q₁}, {q₀,q₁}}.
δ(q₁,a) = {q₄,q₅}
Baca: “Apabila berada di q satu dan membaca a, state destinasi yang mungkin ialah q empat dan q lima.”
δ(q₀,b) = ∅
Baca: “Apabila berada di q kosong dan membaca b, tiada state destinasi.”
∅ bermaksud set kosong. Laluan itu tidak boleh meneruskan pembacaan simbol tersebut.
5. Cara membaca graf NFA
• Bulatan ialah state.
• Panah masuk dari luar menandakan initial state.
• Bulatan berganda menandakan accepting state.
• Label pada panah menentukan simbol input yang dibaca.
• Jika dua panah berlabel a keluar daripada state yang sama, kedua-dua destinasi perlu diambil kira selepas membaca SATU a.
• Tiada panah yang sepadan bermaksud laluan itu tersekat.
Set kosong bukan trap state. Set kosong bermaksud tiada kemungkinan state yang tinggal. Trap state pula ialah state sebenar pada graf.
6. Contoh percabangan daripada nota
Gunakan transisi berikut untuk contoh aa:
q₀ —a→ q₁
q₁ —a→ q₄
q₁ —a→ q₅
Diberi F = {q₀,q₅}.
Mula: {q₀}
Baca a pertama: {q₁}
Baca a kedua: {q₄,q₅}
Maka:
δ*(q₀,aa) = {q₄,q₅}
Baca: “Bermula di q kosong, selepas membaca seluruh aa, semua state yang boleh dicapai ialah q empat dan q lima.”
Ada dua kemungkinan laluan:
• q₀ —a→ q₁ —a→ q₄
• q₀ —a→ q₁ —a→ q₅
Input aa diterima kerana laluan kedua berakhir di q₅, iaitu accepting state. Laluan pertama tidak menerima, tetapi itu tidak membatalkan laluan yang menerima.
7. Fungsi transisi lanjutan δ*
δ* : Q × Σ* → P(Q)
Baca: “Delta bintang ialah fungsi daripada Q silang sigma bintang kepada set kuasa Q.”
δ memproses satu simbol. δ* memproses seluruh rentetan, termasuk rentetan kosong.
Untuk memproses simbol seterusnya, cari transisi daripada SETIAP state semasa, kemudian gabungkan semua hasil. State yang sama ditulis sekali sahaja.
Susunan ahli set tidak penting:
{q₄,q₅} = {q₅,q₄}.
Bagi NFA tanpa transisi λ:
δ*(q₀,λ) = {q₀}.
8. Menentukan penerimaan
L(M) = {w ∈ Σ* : δ*(q₀,w) ∩ F ≠ ∅}
Baca: “Bahasa mesin M ialah set semua rentetan w dalam sigma bintang sedemikian sehingga set state yang dicapai selepas membaca w mempunyai sekurang-kurangnya satu ahli yang sama dengan F.”
• ∈: ialah ahli.
• ∩: persilangan, iaitu ahli yang sama dalam dua set.
• ≠ ∅: bukan set kosong.
Contoh:
δ*(q₀,aa) = {q₄,q₅}
F = {q₀,q₅}
{q₄,q₅} ∩ {q₀,q₅} = {q₅}
Persilangan tidak kosong, maka aa diterima.
Tidak perlu semua state hasil berada dalam F. Cukup sekurang-kurangnya satu.
9. Input mesti habis
Sampai di accepting state ketika masih ada input belum menjamin penerimaan.
Contohnya, selepas membaca aa, mesin mungkin berada di q₄ atau q₅. Jika input sebenar ialah aab, simbol b masih perlu dibaca.
Jika q₄ dan q₅ tiada transisi b, kedua-dua laluan tersekat:
δ*(q₀,aab) = ∅.
Maka aab ditolak, walaupun satu laluan pernah sampai di accepting state selepas aa.
10. Pengenalan kepada transisi λ
Sesetengah nota menggunakan istilah NFA untuk merangkumi mesin dengan transisi λ. Mesin ini juga dinamakan λ-NFA atau ε-NFA.
Transisi λ membolehkan mesin bergerak tanpa menggunakan simbol input. λ bukan huruf tambahan dalam alphabet Σ.
Bagi mesin dengan λ-moves:
δ : Q × (Σ ∪ {λ}) → P(Q).
Contoh dalam nota turut mempunyai:
q₁ —b→ q₂
q₂ —λ→ q₃
q₃ —λ→ q₀
Selepas membaca ab:
q₀ —a→ q₁ —b→ q₂.
Kemudian mesin boleh ke q₃ dan q₀ tanpa membaca huruf tambahan:
q₂ —λ→ q₃ —λ→ q₀.
Oleh itu:
δ*(q₀,ab) = {q₂,q₃,q₀}.
Input ab diterima kerana q₀ ialah ahli F dalam contoh ini.
Penerangan terperinci tentang λ-closure dan pemprosesan λ-moves disambung dalam tajuk 2.4.
11. Kesilapan yang perlu dielakkan
• Jangan pilih satu cabang sahaja; ambil kira semua kemungkinan.
• Dua panah berlabel a tidak bermaksud membaca aa. Setiap laluan menggunakan satu a untuk transisi itu.
• Jangan tentukan penerimaan sebelum seluruh input habis.
• Jangan anggap state terakhir mesti satu sahaja; hasil NFA ialah set state.
• Jangan keliru ∅ dengan λ: ∅ ialah set kosong, λ ialah rentetan kosong.
• Status accepting bergantung pada bulatan berganda atau set F, bukan nama state.
12. Bahasa yang Diterima oleh NFA — Contoh Nota
Bahasa L(M) ialah SET SEMUA rentetan yang diterima oleh mesin M, bukan sekadar satu contoh input yang diterima.
Untuk contoh muka surat 68–76, gunakan mesin berikut:
• Q = {q₀,q₁,q₂,q₃,q₄,q₅}
• Σ = {a,b}
• Initial state: q₀
• Accepting states: F = {q₀,q₅}
Transisinya:
• q₀ —a→ q₁
• q₁ —a→ q₄
• q₁ —a→ q₅
• q₁ —b→ q₂
• q₂ —λ→ q₃
• q₃ —λ→ q₀
Transisi lain yang tidak dilukis dianggap tiada. Khususnya, q₄ dan q₅ tiada panah keluar.
Penting: nama state dalam contoh ini tidak mempunyai fungsi yang sama seperti graf DFA abba. Di sini q₅ ialah accepting state, bukan trap state.
13. Cara Membaca Formula Penerimaan NFA
L(M) = {w ∈ Σ* : δ*(q₀,w) ∩ F ≠ ∅}
Baca:
“Bahasa mesin M ialah set semua rentetan w dalam sigma bintang sedemikian sehingga set state yang dicapai selepas membaca seluruh w mempunyai sekurang-kurangnya satu ahli yang sama dengan set accepting states F.”
• δ*(q₀,w): semua state yang boleh dicapai selepas seluruh w dibaca, termasuk pergerakan λ yang mungkin.
• ∩ F: cari state yang turut berada dalam F.
• ≠ ∅: hasil persilangan bukan set kosong.
Satu laluan yang menerima sudah mencukupi. Input ditolak hanya apabila tiada laluan yang menerima seluruh input.
14. Contoh aa — Diterima
Mula: {q₀}
Baca a pertama: {q₁}
Baca a kedua: {q₄,q₅}
δ*(q₀,aa) = {q₄,q₅}
Semak accepting states:
{q₄,q₅} ∩ {q₀,q₅} = {q₅}
Maka aa ∈ L(M).
Baca: “aa ialah ahli bahasa mesin M.”
Laluan ke q₄ tidak menerima, tetapi laluan ke q₅ menerima. Oleh itu, seluruh input aa diterima.
15. Contoh ab — Diterima
q₀ —a→ q₁ —b→ q₂
Input ab sudah habis di q₂. Mesin masih boleh mengambil transisi λ tanpa menggunakan huruf tambahan:
q₂ —λ→ q₃ —λ→ q₀
δ*(q₀,ab) = {q₂,q₃,q₀}
Ketiga-tiganya termasuk kerana kita boleh mengambil sifar, satu atau dua transisi λ selepas sampai di q₂.
{q₂,q₃,q₀} ∩ {q₀,q₅} = {q₀}
Maka ab ∈ L(M).
16. Contoh abaa — Diterima
Input: a, b, a, a.
• Baca a: q₀ ke q₁.
• Baca b: q₁ ke q₂.
• Ikut λ: q₂ ke q₃, kemudian ke q₀. Baki input masih aa.
• Baca a: q₀ ke q₁.
• Baca a terakhir: q₁ ke q₄ atau q₅.
δ*(q₀,abaa) = {q₄,q₅}
Oleh sebab q₅ ∈ F, maka abaa ∈ L(M).
Pembetulan slide 74:
Sebelah kanan sepatutnya tertulis “abaa ∈ L(M)”, sepadan dengan input abaa pada sebelah kiri.
Rentetan aaba pula ditolak: selepas aa, mesin berada di q₄ atau q₅ dan kedua-duanya tiada transisi b. Input aaba tidak dapat dihabiskan.
17. Contoh aba — Ditolak
Selepas ab:
{q₂,q₃,q₀}
Baca a terakhir:
• q₂ tiada transisi a secara langsung.
• q₃ tiada transisi a secara langsung.
• q₀ mempunyai transisi a ke q₁.
Pergerakan λ telah diambil kira dalam set semasa, maka hasilnya:
δ*(q₀,aba) = {q₁}
{q₁} ∩ {q₀,q₅} = ∅
Maka aba ∉ L(M).
Baca: “aba bukan ahli bahasa mesin M.”
Input sudah habis, tetapi tiada kemungkinan state akhir yang accepting.
18. Rentetan Kosong λ — Diterima
Mesin boleh kekal di initial state tanpa membaca apa-apa.
Dalam contoh ini, tiada transisi λ keluar dari q₀:
δ*(q₀,λ) = {q₀}
Oleh sebab q₀ ∈ F, rentetan kosong diterima:
λ ∈ L(M).
Ini berlaku kerana q₀ ialah accepting state, bukan semata-mata kerana ia initial state.
19. Daripada Contoh kepada Seluruh Bahasa
Perhatikan satu pusingan:
q₀ —a→ q₁ —b→ q₂ —λ→ q₃ —λ→ q₀
Satu pusingan membaca ab dan membawa mesin semula ke q₀. Oleh sebab q₀ accepting, mesin menerima:
λ, ab, abab, ababab, ...
Mesin boleh membuat sifar atau beberapa pusingan ab, kemudian mengambil laluan aa ke accepting state q₅. Maka turut diterima:
aa, abaa, ababaa, abababaa, ...
Selepas sampai di q₅, tiada input tambahan boleh dibaca kerana q₅ tiada panah keluar.
Oleh itu, semua rentetan yang diterima mempunyai salah satu bentuk:
• (ab)ⁿ, dengan n ≥ 0.
• (ab)ⁿaa, dengan n ≥ 0.
20. Rumusan Bahasa yang Betul
L(M) = { (ab)ⁿ : n ≥ 0 } ∪ { (ab)ⁿaa : n ≥ 0 }
Bentuk ringkas yang setara:
L(M) = {ab}* ∪ {ab}*{aa}
Atau:
L(M) = {ab}*({λ} ∪ {aa})
Dalam notasi ungkapan regular:
(ab)*(λ ∪ aa)
Cara baca:
“Ulang pasangan ab sifar kali atau lebih, kemudian berhenti atau tambah aa di hujung.”
• Bintang *: sifar ulangan atau lebih.
• ∪: gabungan atau pilihan antara dua set.
• Penulisan bersebelahan: cantuman rentetan.
• Sifar ulangan ab menghasilkan λ.
Contoh n:
n = 0: λ atau aa
n = 1: ab atau abaa
n = 2: abab atau ababaa
n = 3: ababab atau abababaa
Pembetulan slide 76:
Formula pada slide ialah {λ} ∪ {ab}*{aa}. Berdasarkan graf dan F = {q₀,q₅}, formula itu tidak menyenaraikan ab, abab dan ulangan ab yang lain, walaupun mesin menerimanya.
Gunakan rumusan yang dibetulkan:
L(M) = {ab}* ∪ {ab}*{aa}.
21. Semakan Pantas
• λ: diterima; kekal di q₀ yang accepting.
• a: ditolak; berakhir di q₁.
• aa: diterima; salah satu laluan berakhir di q₅.
• ab: diterima; transisi λ boleh membawa mesin ke q₀.
• aba: ditolak; berakhir di q₁.
• abab: diterima; dua pusingan ab kembali ke q₀.
• abaa: diterima; satu pusingan ab diikuti aa.
• aaba: ditolak; tiada transisi b selepas sampai di q₄ atau q₅.
• aaa: ditolak; tiada transisi a keluar dari q₄ atau q₅.
Rumusan ini khusus untuk graf contoh tersebut. Untuk NFA lain, tentukan semula initial state, F dan semua transisi sebelum merumuskan L(M).
Preview Percuma
Lesson Practice
Latihan 3.1 Nondeterministic Finite Automata (NFA)
Cuba Preview
Pelajaran
4
Sambungan NFA dan Reduction of States — 25 Oktober 2026
Tajuk
1
4.1 Finite Automata dengan λ-Moves
Preview Percuma
Lesson Practice