Automata Hingga dan Bahasa Reguler

Automata hingga adalah mesin komputasi paling sederhana, yang membaca masukan satu simbol pada satu waktu hanya dengan menggunakan sejumlah terbatas status internal, dan bahasa yang dikenali oleh automata ini adalah bahasa reguler.

Definition

Automata hingga adalah mesin dengan himpunan status hingga, fungsi transisi pada simbol masukan, status awal, dan status penerima; automata ini menerima sebuah string jika pembacaan string tersebut mengarahkannya dari status awal ke status penerima, dan himpunan string yang diterima adalah bahasanya.

Scope

Topik ini mencakup automata hingga deterministik dan nondeterministik, kesetaraannya melalui konstruksi himpunan bagian, ekspresi reguler dan teorema Kleene, teorema Myhill–Nerode dan minimisasi status, properti penutupan bahasa reguler, dan lemma pemompaan yang digunakan untuk membuktikan bahwa bahasa tertentu tidak reguler.

Core questions

• Bahasa apa saja yang dapat dikenali hanya dengan menggunakan jumlah memori yang tetap dan terbatas?
• Mengapa automata hingga deterministik dan nondeterministik memiliki kekuatan yang sama?
• Bagaimana cara membuktikan bahwa suatu bahasa tertentu tidak reguler?
• Apa automata terkecil yang mengenali bahasa reguler tertentu?

Key theories

Konstruksi himpunan bagian

Setiap automata hingga nondeterministik dapat disimulasikan oleh automata deterministik yang statusnya adalah himpunan dari status asli, membuktikan bahwa kedua model mengenali bahasa yang persis sama.

Teorema Kleene

Suatu bahasa dikenali oleh automata hingga jika dan hanya jika dijelaskan oleh ekspresi reguler, yang menetapkan kesetaraan deskripsi mesin dan aljabar dari bahasa reguler.

Teorema Myhill–Nerode

Suatu bahasa bersifat reguler tepat ketika relasi ketidakterbedaan stringnya memiliki sejumlah kelas yang terbatas, dan kelas-kelas ini menentukan automata deterministik minimal yang unik untuk bahasa tersebut.

Clinical relevance

Automata hingga adalah mesin di balik pencocokan ekspresi reguler, pemindai dan penganalisis leksikal dalam kompiler, pencarian dan penggantian dalam editor teks, dan deteksi pola dalam sistem intrusi jaringan, di mana pengenalan memori terbatas membuat pemrosesan cepat dan dapat diprediksi.

History

Berdasarkan model jaringan saraf McCulloch dan Pitts tahun 1943, Kleene mengkarakterisasi peristiwa yang dapat direpresentasikan oleh automata hingga sekitar tahun 1951, dan Rabin serta Scott memformalkan automata nondeterministik dan masalah keputusannya pada tahun 1959, sebuah karya yang kemudian diakui dengan Penghargaan Turing.

Key figures

• Stephen Kleene
• Michael Rabin
• Dana Scott
• Anil Nerode

Seminal works

• rabinScott1959
• sipser2013

Frequently asked questions

Bagaimana cara menunjukkan bahwa suatu bahasa tidak reguler?

Alat yang paling umum adalah lemma pemompaan, yang menyatakan bahwa setiap string yang cukup panjang dalam bahasa reguler mengandung substring yang dapat diulang berkali-kali sambil tetap berada dalam bahasa tersebut. Menemukan string yang tidak dapat dipompa dengan cara ini membuktikan bahwa bahasa tersebut tidak reguler; teorema Myhill–Nerode memberikan argumen alternatif dengan menunjukkan prefiks yang tak terbatas banyaknya yang dapat dibedakan.

Jika automata nondeterministik tidak lebih kuat, mengapa menggunakannya?

Automata nondeterministik seringkali jauh lebih kecil dan lebih mudah dirancang atau diturunkan dari ekspresi reguler. Konstruksi himpunan bagian dapat mengubahnya ke bentuk deterministik bila diperlukan, dengan kemungkinan biaya eksponensial dalam jumlah status, sehingga nondeterminisme adalah alat spesifikasi yang nyaman daripada peningkatan kekuatan pengenalan.