Seberapa praktis Teori Automata?

Selalu ada cara untuk aplikasi dalam topik yang berkaitan dengan ilmu komputer teoretis. Tetapi buku teks dan program sarjana biasanya tidak menjelaskan alasan bahwa teori automata adalah topik penting dan apakah masih memiliki aplikasi dalam praktiknya. Oleh karena itu mahasiswa sarjana mungkin mengalami kesulitan dalam memahami pentingnya teori automata dan mungkin berpikir itu bukan penggunaan praktis lagi.

Apakah teori automata masih berguna dalam praktik?

Haruskah itu menjadi bagian dari kurikulum CS sarjana?

1. Pernah menggunakan alat seperti grep / awk / sed? Ekspresi reguler membentuk jantung dari alat ini.

2. Anda akan terkejut betapa banyak pengkodean yang dapat Anda hindari dengan menggunakan prinsip ekspresi reguler - dalam "proyek praktis", seperti server email.

3. Jika Anda seorang CS mayor, Anda pasti akan menulis kompiler / juru bahasa untuk (setidaknya sedikit) bahasa Jika Anda pernah mencoba tugas ini sebelumnya dan terjebak, Anda akan menghargai betapa sedikit teori (alias tata bahasa bebas konteks) dapat membantu Anda. Teori ini telah membuat tugas yang sebelumnya mustahil menjadi sesuatu yang dapat diselesaikan selama akhir pekan. (Dan itu memenangkan penemu penghargaan Turing - google BNF).

4. Jika Anda seorang CS mayor, pada titik tertentu, Anda perlu duduk dan berpikir tentang dasar filosofis komputasi, dan bukan hanya tentang betapa kerennya versi Android API selanjutnya. Pada catatan terkait, adalah tugas universitas untuk tidak mempersiapkan Anda untuk 5 tahun ke depan dalam hidup Anda, tetapi untuk mempersiapkan Anda untuk 50 tahun ke depan. Satu-satunya hal yang dapat mereka lakukan dalam hal ini adalah membantu Anda berpikir - berpikir teori automata sebagai salah satu program studi tersebut.

Salah satu manifestasi yang lebih praktis dari CS adalah Konstruksi Kompiler. Pada tahun 1965, Knuth memulai studi parser LR. Dengan cepat (dalam waktu kurang dari satu dekade), kami memiliki parser LALR yang merupakan bagian dari automata pushdown deterministik yang memungkinkan kami untuk menerapkan parser shift / pengurangan.

Di jantung kelayakan dan efisiensi penguraian LALR adalah bukti (oleh Knuth) bahwa "awalan" bahasa berubah menjadi biasa (otomat terbatas Anda). Ini adalah asal mula generator pengurai otomatis seperti yacc / bison dll.

Aman untuk mengatakan bahwa bahasa pemrograman seperti yang kita tahu mereka berutang banyak efisiensi kompilasi mereka untuk perkembangan ini.

Berikut adalah contoh lain: inti dari protokol TCP / IP adalah mesin keadaan terbatas. Seberapa jauh lebih praktis bisa didapat?

Setiap siswa CS yang serius, terutama yang praktis, harus memperhatikan teori automata. Ini adalah dasar bagi banyak kekayaan Ilmu Komputer.

Bisakah Anda mendengar suara itu ? Ini adalah suara dari ribuan teorema, aplikasi, dan alat-alat yang menertawakan surga automata-teoretik.

Bahasa dan automata adalah konsep yang elegan dan kuat yang akan Anda temukan di setiap bidang ilmu komputer. Bahasa tidak kering, formalis tangan-down dari komputasi prasejarah. Perspektif teori bahasa menyaring pertanyaan-pertanyaan yang tampaknya rumit tentang benda-benda yang rumit dan buram menjadi pernyataan sederhana tentang kata-kata dan pohon. Bahasa formal memainkan peran dalam ilmu komputer yang mirip dengan sudut pandang mendasar dan mengubah permainan yang dibawa oleh aljabar dan topologi ke matematika klasik. Berikut adalah beberapa masalah praktis, cukup rumit, praktis yang didekati melalui teori bahasa.

1. Anda ingin melihat duplikat frasa dalam dokumen dan menghapus yang kedua kalinya. Intinya, Anda ingin mengganti urutan dalam bahasa.
2. Apakah suatu program mengandung pelanggaran asersi? Apakah driver perangkat menghormati protokol tertentu saat berinteraksi dengan kernel? Perilaku suatu program adalah serangkaian eksekusi; dengan kata lain, bahasa. Properti kebenaran adalah bahasa lain. Masalah kebenaran program berjumlah cek inklusi bahasa.
3. Bisakah perangkat lunak Anda macet dalam loop tak terbatas? Apakah algoritma terdistribusi mengandung livelock? Kita membutuhkan bahasa di atas kata-kata yang tak terbatas, tetapi tampilan penyertaan bahasa masih berlaku.
4. Anda ingin membangun pembersih untuk mendeteksi Javascript berbahaya yang dimasukkan ke dalam aplikasi web. Set string berbahaya adalah bahasa. Set string dimasukkan ke dalam formulir dalam bahasa lain. Anda ingin menentukan apakah persimpangan bahasa-bahasa ini tidak kosong.
5. Pemantauan run-time dari sistem reaktif dan misi-kritis. Anda ingin merancang monitor perangkat lunak yang mengawasi operasi proses kimia Anda atau melacak pembaruan ke basis data keuangan. Ini adalah masalah inklusi dan persimpangan bahasa jantung.
6. Pengenalan pola dengan banyak aplikasinya. Anda ingin mendeteksi pola dalam data genom, dalam teks, dalam serangkaian laporan bug. Ini adalah masalah di mana kita diberikan kata-kata dari bahasa yang tidak dikenal dan harus menebak bahasa itu. Ini adalah masalah inferensi bahasa.
7. Diberikan seperangkat dokumen XML, Anda ingin merekayasa balik skema yang berlaku untuk dokumen-dokumen ini. Dokumen XML dapat diidealkan sebagai pohon. Skema kemudian merupakan spesifikasi bahasa pohon dan masalah inferensi skema adalah masalah inferensi bahasa atas bahasa pohon.
8. Banyak aplikasi memerlukan penalaran aritmatika otomatis. Misalkan kita memperbaiki teori logis seperti aritmatika Presburger, di mana kita memiliki bilangan asli, penjumlahan, dan predikat kurang dari itu. Rumus dengan variabel n mewakili seperangkat vektor n-dimensi. Vektor adalah urutan angka dan dapat dikodekan sebagai kata. Predikat adalah seperangkat kata; sebuah bahasa. Operasi logis seperti konjungsi, disjungsi, dan negasi menjadi persimpangan, penyatuan dan pelengkap bahasa (kuantifikasi eksistensial adalah semacam proyeksi).

Pengurangan mengisyaratkan di atas memperlakukan bahasa sebagai objek matematika abstrak. Untuk menerapkan ide-ide ini dalam praktiknya, kita membutuhkan struktur data untuk mewakili bahasa dan algoritma untuk memanipulasi struktur data ini.

Masukkan automata. Automata memungkinkan kita mengurangi pertanyaan tentang objek matematika abstrak seperti bahasa menjadi konkret, pertanyaan algoritmik tentang grafik berlabel. Teori bahasa dan automata, di samping sejumlah aplikasi praktis yang gila, menyediakan layanan intelektual yang sangat signifikan. Kita dapat memikirkan masalah mulai dari memformat kode pos hingga prosedur pengambilan keputusan untuk logika urutan kedua monadik dalam ruang konseptual yang seragam dan tidak berantakan. Betapa menakjubkannya itu!

Saya tidak mengatakan apa pun tentang logika dan prosedur pengambilan keputusan. (Ya, mereka memiliki aplikasi praktis.) Lihat jawaban Kaveh untuk ikhtisar otoritatif.

Seperti yang dijelaskan dalam jawaban lain, teori automata penting secara konseptual sebagai model komputasi sederhana yang kami pahami dengan baik, dan ekspresi reguler dan automata memiliki banyak aplikasi kehidupan nyata.

Berikut adalah contoh kecil untuk penelitian modern yang kembali ke teori automata untuk memahami konsep modern. Dalam makalah ini peneliti membuktikan bahwa semua bahasa reguler memiliki penguji properti: "Bahasa reguler dapat diuji dengan jumlah permintaan yang konstan"

Ini bukan hanya vanilla automatons. Anda sedang belajar tentang dasar-dasar (negara penerima, transisi epsilon, ...) dari model (komputasi) yang membantu dalam penalaran tentang apa yang bisa, dan yang lebih penting apa yang tidak bisa diungkapkan dengan beberapa bahasa permintaan. Beberapa hasil menarik termasuk:

• ya, hasil yang terkenal adalah bahwa Deterministic Finite Automatons mengenali bahasa reguler - jadi sekarang Anda tahu apa yang Anda butuhkan untuk menerapkan pencocokan ekspresi reguler.
• Pushdown Automata mengenali tata bahasa bebas konteks - sekarang Anda memiliki gagasan tentang seperti apa parser itu (atau setidaknya kelas besar dari mereka).
• automata pohon mengenali pernyataan dari logika urutan kedua monadik - sekarang Anda memiliki gagasan tentang apa yang diperlukan untuk mengimplementasikan beberapa bahasa pemrograman kendala, atau ... beberapa pernyataan dalam SQL , misalnya.

(dan tentu saja saya melewatkan banyak kelas lain)

Pada dasarnya, ini adalah model yang sangat umum. Kelas Anda mungkin akan menekankan tautan antara automata, bahasa, dan logika.

Jika saya melihat menghubungkan ini dengan alat-alat konkret "duniawi", saya akan menghabiskan pagi yang santai di perpustakaan membaca beberapa bagian (AB?) Dari Yayasan Database oleh Abiteboul & al, dan mencoba untuk menghubungkan ini kembali ke materi kelas . Tentu saja itu hanya salah satu dari (banyak) cara mencari aplikasi kelas automata, dan saya kira bukan yang paling jelas - tetapi itulah mengapa ini merupakan latihan yang menarik.

Seperti yang telah ditunjukkan dalam berbagai jawaban, Teori Automata dalam kursus UG memberikan satu kerangka kerja konseptual dasar untuk memperkenalkan topik yang lebih maju (dan praktis), dan juga untuk menunjukkan koneksi yang diabaikan; misalnya: Diagram Keputusan Biner (mereka diminimalkan DFA; setelah mengajar DFA, saya sering mengajar pemecahan puzzle berbasis BDD); scripting termasuk dalam BioPerl dan BioPython (dan pengaturan yang bagus untuk memperkuat berapa banyak kecocokan yang tidak diinginkan dapat disembunyikan di skrip dunia nyata skrip), debugging formal (properti negara sebagai negated FA, intersect), dan bahkan VCR atau pemrograman alarm penyusup rumah (Setiap hari situasi stres dari robot yang ditentukan dengan buruk diajarkan melalui contoh tidak lengkap; mungkin diformalkan menggunakan Harel's play-in / play-out skenario berdasarkan sintesis antarmuka pengguna). Saya juga menggunakan pengaturan untuk mengajar Python '

Saya akan membuang jawaban lain dari sudut praktis yang sama sekali berbeda: mesin negara yang terbatas (atau setidaknya beberapa generalisasi / ekstensi dari mereka) sering digunakan pada sisi AI dari pemrograman game. Mereka ternyata menyediakan model yang sangat baik untuk merangkum perilaku karakter; misalnya, musuh mungkin memiliki negara yang mewakili 'patroli', 'pencarian', 'pendekatan', 'serangan', 'pertahanan', 'mundur', 'mati', dll. dengan transisi yang jelas di antara mereka. Ini tidak melibatkan aspek formal automata seperti bahasa reguler dan sejenisnya, tetapi konsep automaton adalah yang paling inti.

Kita telah melihat bahwa bahasa yang mengontraskan teori dan praktik, menempatkan yang di atas yang lain, adalah penyempurnaan dari ketidaktahuan — bahwa itu membuktikan bahwa seseorang tidak mengenal unsur-unsur pemikiran yang pertama, dan berjalan dengan baik menuju pembuktiannya. pikiran menjadi sesat sehingga tidak mampu diajari mereka.

- James Mill (menulis dengan nama samaran sebagai "PQ"), "Teori dan Praktek", London dan Westminster Review , April 1836

Ada banyak penelitian yang berkaitan dengan teori automata dalam pengecekan model yang digunakan dalam industri. Lihat kuliah terbaru Moshe Vardi di Fields Institute , khususnya kuliah ke-3 "Logika, Automata, Permainan, dan Algoritma" untuk mengetahui mengapa teori automata masih penting dan bermanfaat.

Abstrak:

Pendekatan automata-teoretis untuk prosedur pengambilan keputusan, yang diperkenalkan oleh Buechi, Elgot, Rabin dan Trakhtenbrot pada 1950-an dan 1960-an, adalah salah satu pendekatan paling mendasar untuk prosedur pengambilan keputusan. Baru-baru ini, pendekatan ini telah menemukan aplikasi industri dalam verifikasi formal perangkat keras dan sistem perangkat lunak. Jalur dari logika ke algoritma praktis tidak hanya melalui automata, tetapi juga melalui game, yang aspek algoritmiknya dipelajari oleh Chandra, Kozen, dan Stockmeyer pada akhir 1970-an. Dalam pembicaraan tinjauan umum ini kami menjelaskan jalur dari logika ke algoritma melalui automata dan game.

Slide dan file audio ceramah tersedia di sini: 1 , 2 , 3 .

Kita harus mempertimbangkan semantik kata "praktis" dan "aplikasi". Bagi sebagian siswa, praktik adalah segala sesuatu yang akan membantu mereka lulus ujian; untuk orang lain, apa pun yang akan muncul dalam suatu pekerjaan. Dalam kedua kasus tersebut, Teori Automata memang sangat praktis.

Seperti yang ditunjukkan orang lain, Anda akan menggunakan tata bahasa, misalnya, saat mempelajari kompiler. Tetapi bahkan lebih dari itu: memahami seluruh konsep memiliki keadaan yang berbeda dan aturan untuk transisi di antara mereka dapat membuat Anda seorang programmer yang lebih baik ketika Anda menyadari, misalnya, bahwa kode Anda berlebihan di sana-sini, dan bahwa ketika Anda memperbaikinya, Anda yang menerapkan dalam kode Anda sama ide-ide konseptual belakang DFA minimalisasi.

Demikian pula untuk "aplikasi". Apa yang Anda mengerti dari kata itu? Bahkan jika Anda adalah seorang "insinyur yang membumi", Anda akan melihat dan menggunakan ide-ide yang mirip dengan Automata Theory dalam proyek-proyek dunia nyata: kode pemrograman, diagram alir, dan bahkan konsep stack yang sederhana namun cemerlang. Untuk kutu buku teori seperti saya, saya mempertimbangkan aplikasi Teori Automata di bidang lain, seperti logika, aljabar dan teori model hingga. Tentunya, saya mungkin tidak akan pernah perlu menggunakan lemma pemompaan saat berbelanja di supermarket, tetapi teorema seperti itu telah membantu saya memahami struktur kelas bahasa tertentu, belum lagi logika dan struktur aljabar yang berhubungan dengannya. Dan itu adalah sesuatu yang saya hargai lebih dari ukuran praktisnya.

Disatukan dengan logika, automata dapat menawarkan cara untuk memeriksa status statemens

$\qquad A \models \varphi$

$A$$\varphi$$A$$\varphi$

$\varphi$$A$$\varphi$$A_\varphi$$\cal{L}(A) \subseteq \cal{L}(A_\varphi)$

Finite Automata, sering ditulis sebagai mesin keadaan terbatas dalam konteks yang berbeda, atau dengan varian probabilistiknya. Hidden Markov Models dapat diterapkan pada pengenalan pola dan struktur kuantifikasi suatu pola. Misalnya apa yang merupakan automata terbatas stokastik terkecil yang akan menghasilkan string sesuai, lebih atau kurang, untuk distribusi probabilitas yang diberikan, atau mencocokkan sifat statistik dari sampel string (atau seri waktu) dari beberapa distribusi.

Lihat misalnya CSSR , sebuah algoritma untuk rekonstruksi tersembunyi yang tersembunyi; lebih efisien dan fleksibel daripada Hidden Markov Models.

Aplikasi lain yang lebih praktis dari teori automata adalah pengembangan kecerdasan buatan. Inteligensi buatan dikembangkan dari konsep otomat terbatas. Jaringan saraf robot dibangun berdasarkan teori automata. Lagipula robot juga automata.

Beberapa telah memberikan jawaban yang bagus dalam hal hubungannya dengan industri. Apa yang seharusnya penting adalah nilai ilmiahnya, dan teori Automata sering kali menjadi pintu masuk untuk pertama-tama memahami teori komputasi tingkat tinggi dalam studi mahasiswa sarjana. Teori Automata memiliki seperangkat teorema besar yang muncul di semua tempat di Theoretical Computer Science, dan terutama ketika seseorang ingin berbicara tentang aplikasi seperti Compiler. Nilai ilmiahnya (tidak ketinggalan zaman, bagaimana mungkin? Ini adalah teori inti di lapangan). Praktis bagi setiap ilmuwan yang tertarik pada komputasi. Ini praktis karena pengetahuan yang berguna bagi mereka yang mengerti atau ingin memahami sifat perhitungan. Jika Anda tidak dapat menggunakannya, saya mempertanyakan penelitian atau bahkan bermaksud mempelajari CS karena bukan pemrograman (itu '