Teori Bahasa Formal dan Otomata

Teori bahasa formal dan mesin abstrak yang mengenalinya, menyediakan kosakata untuk menjelaskan seberapa kompleks suatu pola linguistik dan algoritma apa yang dapat memprosesnya.

Definition

Teori bahasa formal mempelajari himpunan string yang didefinisikan oleh tata bahasa, dan teori otomata mempelajari mesin abstrak yang menentukan keanggotaan dalam himpunan tersebut.

Scope

Mencakup hierarki Chomsky (bahasa reguler, bebas konteks, peka konteks, dapat dihitung secara rekursif), tata bahasa yang sesuai, dan otomata pengenal — mesin keadaan terbatas, otomata tumpukan, dan mesin Turing. Ini membahas sifat penutupan dan keterdecidabilitas yang relevan dengan pemrosesan bahasa dan pertanyaan tentang posisi bahasa alami dalam hierarki. Lemma pemompaan dan bukti kompleksitas penuh diperlakukan sebagai latar belakang daripada konten utama.

Core questions

• Otomata mana yang sesuai dengan setiap tingkat hierarki Chomsky?
• Di mana posisi bahasa alami dalam hierarki, dan mengapa dikatakan melebihi kekuatan bebas konteks?
• Apa artinya suatu kelas bahasa tertutup di bawah suatu operasi, dan mengapa hal itu penting untuk rekayasa?

Key concepts

• bahasa reguler
• tata bahasa bebas konteks
• tata bahasa peka konteks
• otomata keadaan terbatas
• otomata tumpukan
• mesin Turing
• sifat penutupan
• kepekaan konteks ringan

Key theories

Hierarki Chomsky

Empat kelas bahasa formal yang saling bersarang, masing-masing dihasilkan oleh jenis tata bahasa terbatas dan dikenali oleh otomata yang sesuai, mengurutkan konstruksi linguistik berdasarkan kekuatan komputasi yang dibutuhkan.

Korespondensi Tata Bahasa–Otomata

Setiap kelas tata bahasa terbukti setara dengan kelas mesin — tata bahasa reguler dengan otomata terbatas, tata bahasa bebas konteks dengan otomata tumpukan — menghubungkan deskripsi generatif dengan algoritma pengenalan.

History

Makalah Chomsky tahun 1956 memperkenalkan hierarki sebagai bagian dari argumen bahwa model keadaan terbatas tidak memadai untuk bahasa alami. Dekade-dekade berikutnya memformalkan korespondensi otomata, dan ahli linguistik komputasi kemudian menunjukkan bahwa bahasa alami paling banyak membutuhkan kekuatan 'agak peka konteks' (mildly context-sensitive), memotivasi formalisme tata bahasa di luar bebas konteks.

Debates

Apakah bahasa alami bebas konteks?

Ketergantungan silang (cross-serial dependencies) dalam bahasa seperti bahasa Jerman Swiss digunakan untuk berargumen bahwa bahasa alami melebihi kekuatan bebas konteks, mengarah pada gagasan kepekaan konteks ringan (mild context-sensitivity) sebagai tingkat ekspresivitas yang tepat.

Key figures

• Noam Chomsky
• John Hopcroft
• Jeffrey Ullman
• Stephen Kleene

Seminal works

• chomsky1956
• hopcroft2006

Frequently asked questions

Apa perbedaan antara bahasa reguler dan bahasa bebas konteks?

Bahasa reguler dapat dikenali dengan memori terbatas oleh otomata keadaan terbatas; bahasa bebas konteks mungkin memerlukan tumpukan (otomata tumpukan) untuk melacak struktur bersarang, seperti tanda kurung seimbang atau klausa tertanam.