Hierarki Chomsky

Hierarki Chomsky mengorganisasi bahasa formal ke dalam empat kelas bersarang, masing-masing didefinisikan oleh pembatasan pada aturan tata bahasa dan dicocokkan dengan jenis mesin abstrak yang berbeda.

Definition

Hierarki Chomsky adalah klasifikasi tata bahasa formal berdasarkan pembatasan yang semakin kuat pada aturan produksinya, menghasilkan kelas bahasa reguler, bebas konteks, peka konteks, dan dapat dihitung secara rekursif dalam rantai inklusi yang ketat.

Scope

Topik ini mencakup empat jenis tata bahasa — tidak terbatas, peka konteks, bebas konteks, dan reguler — inklusi ketatnya, dan model automata yang sesuai dengan setiap tingkatan, yaitu mesin Turing, automata terbatas linear, automata pushdown, dan automata hingga, bersama dengan sifat penutupan dan keterdecidabilitas yang memisahkan tingkatan-tingkatan tersebut.

Core questions

• Bagaimana pembatasan pada aturan tata bahasa diterjemahkan menjadi batasan pada memori dan daya komputasi?
• Mengapa setiap tingkatan hierarki secara ketat terkandung dalam tingkatan berikutnya?
• Model automata mana yang sesuai dengan setiap jenis tata bahasa?
• Bagaimana sifat keterdecidabilitas dan penutupan berubah seiring dengan kenaikan hierarki?

Key theories

Korespondensi Tata Bahasa–Mesin

Setiap kelas tata bahasa dikenali oleh model mesin tertentu — reguler oleh automata hingga, bebas konteks oleh automata pushdown, peka konteks oleh automata terbatas linear, dan tidak terbatas oleh mesin Turing — menghubungkan deskripsi komputasi generatif dan operasional.

Inklusi Ketat Kelas Bahasa

Setiap tingkatan secara tepat mengandung tingkatan di bawahnya, dibuktikan oleh bahasa pemisah konkret, sehingga hierarki ini adalah tangga kekuatan ekspresif yang asli, bukan kumpulan deskripsi yang setara.

Clinical relevance

Hierarki ini adalah peta pengorganisasi teori bahasa formal: hierarki ini memberi tahu perancang bahasa pemrograman, bahasa kueri, dan spesifikasi protokol berapa banyak mekanisme yang dibutuhkan oleh kelas pola tertentu, dan hierarki ini membingkai batas antara apa yang dapat diputuskan (decidable) dan apa yang hanya dapat dikenali (recognizable).

History

Chomsky mengusulkan hierarki ini pada akhir tahun 1950-an saat mencari model formal sintaksis bahasa alami, dan korespondensi mesin ditetapkan seiring dengan kematangan teori automata sepanjang tahun 1960-an, dengan automata terbatas linear diperkenalkan oleh Myhill dan tingkat peka konteks diklarifikasi oleh Kuroda.

Key figures

• Noam Chomsky
• Marcel-Paul Schützenberger
• John Myhill

Seminal works

• hopcroft2006
• sipser2013

Frequently asked questions

Apa saja empat tingkatan hierarki Chomsky?

Dari yang paling tidak kuat hingga paling kuat adalah bahasa reguler (Tipe 3), bahasa bebas konteks (Tipe 2), bahasa peka konteks (Tipe 1), dan bahasa yang dapat dihitung secara rekursif (Tipe 0). Setiap tingkatan melonggarkan pembatasan pada aturan tata bahasa dan sesuai dengan mesin dengan memori yang lebih besar.

Apakah bahasa alami tercakup dalam hierarki Chomsky?

Hierarki ini awalnya dimotivasi oleh linguistik, tetapi sebagian besar ahli bahasa menyimpulkan bahwa bahasa alami tidak bebas konteks, berada pada tingkatan yang sering disebut peka konteks ringan. Hierarki ini tetap menjadi dasar dalam ilmu komputer meskipun bahasa manusia hanya cocok secara longgar.