Automata dan Bahasa Formal
Teori automata dan bahasa formal mempelajari mesin-mesin ideal dengan kekuatan yang meningkat dan kelas-kelas string, atau bahasa, yang dapat dikenali oleh masing-masing mesin, memberikan penjelasan matematis yang tepat tentang apa yang dianggap sebagai pola dan apa yang diperlukan untuk mendeteksinya.
Definition
Bahasa formal adalah sekumpulan string terbatas di atas alfabet tetap, dan automata adalah perangkat komputasi abstrak yang komputasi penerimaannya mendefinisikan bahasa tersebut; area ini mengklasifikasikan bahasa berdasarkan jenis automata atau tata bahasa paling sederhana yang menghasilkan atau mengenalinya.
Scope
Area ini mencakup automata hingga (finite automata) dan bahasa reguler, automata pushdown dan bahasa bebas konteks, hierarki Chomsky yang menghubungkan tata bahasa dengan model mesin, sifat penutupan (closure properties) dan keputusan (decision properties) dari kelas bahasa, serta automata yang memproses kata dan pohon tak terbatas, bersama dengan karakterisasi aljabar dan logis yang menyertainya.
Sub-topics
Core questions
- Bahasa apa saja yang dapat dikenali oleh mesin dengan memori terbatas, dan apa yang tidak dapat dikenali?
- Bagaimana tata bahasa dan model mesin saling berhubungan di seluruh tingkatan hierarki Chomsky?
- Pertanyaan mana tentang kelas bahasa, seperti kekosongan (emptiness) atau kesetaraan (equivalence), yang dapat diputuskan secara algoritmik?
- Bagaimana automata diperluas ke kata dan pohon tak terbatas, dan mengapa ini penting untuk verifikasi?
Key theories
- Kesetaraan automata hingga deterministik dan non-deterministik
- Setiap automata hingga non-deterministik dapat dikonversi dengan konstruksi subset menjadi automata deterministik yang menerima bahasa yang sama, sehingga non-determinisme tidak menambah kekuatan pengenalan pada tingkat keadaan hingga meskipun dapat secara eksponensial lebih ringkas.
- Teorema Kleene
- Bahasa yang dikenali oleh automata hingga adalah persis bahasa reguler yang dijelaskan oleh ekspresi reguler, mengaitkan pandangan mesin, aljabar, dan tata bahasa dari kelas bahasa paling sederhana.
- Hierarki Chomsky
- Bahasa reguler, bebas konteks, sensitif konteks, dan rekursif terhitung membentuk rantai inklusi yang ketat, dengan setiap tingkatan disesuaikan dengan jenis tata bahasa dan model automata dari struktur memori yang sesuai.
Clinical relevance
Automata hingga dan ekspresi reguler mendukung analisis leksikal dalam kompiler, pencarian teks, dan spesifikasi protokol, sementara tata bahasa bebas konteks mendasari penguraian bahasa pemrograman; automata pada objek tak terbatas membentuk inti algoritmik dari pemeriksaan model (model checking), di mana suatu sistem diverifikasi terhadap spesifikasi logika temporal.
History
Model keadaan hingga (finite-state models) muncul dari jaringan saraf McCulloch dan Pitts pada tahun 1940-an dan diberikan bentuk teori bahasa oleh Kleene sekitar tahun 1951. Rabin dan Scott memperkenalkan automata non-deterministik pada tahun 1959, sementara tata bahasa Chomsky dari akhir 1950-an mengorganisir kelas bahasa ke dalam hierarki yang masih menyusun subjek ini.
Key figures
- Stephen Kleene
- Michael Rabin
- Dana Scott
- Noam Chomsky
Related topics
Seminal works
- rabinScott1959
- sipser2013
- hopcroft2006
Frequently asked questions
- Mengapa automata hingga tidak dapat mengenali tanda kurung yang seimbang?
- Mengenali penumpukan (nesting) yang sewenang-wenang membutuhkan penghitungan berapa banyak tanda kurung pembuka yang belum tertutup, yang dapat melebihi jumlah keadaan tetap apa pun. Automata hingga hanya memiliki memori terbatas, sehingga kemampuan penghitungan ini berada satu tingkat lebih tinggi, dengan automata pushdown dan bahasa bebas konteks.
- Apa manfaat praktis dari teori bahasa formal?
- Ini memberi tahu para insinyur pola apa yang dapat diekspresikan oleh alat tertentu. Ekspresi reguler cukup untuk token tetapi tidak untuk struktur bersarang, itulah sebabnya kompiler membagi pekerjaan antara leksikal reguler dan parser bebas konteks, dan mengapa alat verifikasi mengandalkan automata pada kata-kata tak terbatas.