Hệ thống phân cấp Chomsky

Hệ thống phân cấp Chomsky tổ chức các ngôn ngữ hình thức thành bốn lớp lồng nhau, mỗi lớp được định nghĩa bằng một hạn chế về quy tắc ngữ pháp và được ghép nối với một loại máy trừu tượng riêng biệt.

Definition

Hệ thống phân cấp Chomsky là một phân loại các ngữ pháp hình thức bằng các hạn chế ngày càng chặt chẽ hơn đối với các quy tắc sản xuất của chúng, tạo ra các lớp ngôn ngữ chính quy, phi ngữ cảnh, nhạy ngữ cảnh và đếm được đệ quy trong một chuỗi bao hàm chặt chẽ.

Scope

Chủ đề này bao gồm bốn loại ngữ pháp — không hạn chế, nhạy ngữ cảnh, phi ngữ cảnh và chính quy — sự bao hàm chặt chẽ của chúng, và mô hình automaton tương ứng với mỗi cấp độ, cụ thể là máy Turing, automaton bị chặn tuyến tính, automaton đẩy xuống và automaton hữu hạn, cùng với các thuộc tính đóng và tính quyết định phân tách các cấp độ.

Core questions

• Các hạn chế về quy tắc ngữ pháp chuyển thành giới hạn về bộ nhớ và sức mạnh tính toán như thế nào?
• Tại sao mỗi cấp độ của hệ thống phân cấp lại được bao hàm chặt chẽ trong cấp độ tiếp theo?
• Mô hình automaton nào tương ứng với mỗi loại ngữ pháp?
• Các thuộc tính tính quyết định và đóng thay đổi như thế nào khi di chuyển lên hệ thống phân cấp?

Key theories

Sự tương ứng giữa ngữ pháp và máy

Mỗi lớp ngữ pháp được nhận dạng bởi một mô hình máy cụ thể — chính quy bởi automaton hữu hạn, phi ngữ cảnh bởi automaton đẩy xuống, nhạy ngữ cảnh bởi automaton bị chặn tuyến tính, và không hạn chế bởi máy Turing — liên kết các mô tả sinh thành và hoạt động của tính toán.

Sự bao hàm chặt chẽ của các lớp ngôn ngữ

Mỗi cấp độ chứa đúng cấp độ bên dưới nó, được chứng minh bằng các ngôn ngữ phân tách cụ thể, do đó hệ thống phân cấp là một thang bậc thực sự của sức mạnh biểu đạt tăng dần chứ không phải là một tập hợp các mô tả tương đương.

Clinical relevance

Hệ thống phân cấp là bản đồ tổ chức của lý thuyết ngôn ngữ hình thức: nó cho các nhà thiết kế ngôn ngữ lập trình, ngôn ngữ truy vấn và đặc tả giao thức biết một lớp mẫu nhất định yêu cầu bao nhiêu cơ chế, và nó định hình ranh giới giữa cái có thể quyết định và cái chỉ có thể nhận dạng.

History

Chomsky đề xuất hệ thống phân cấp vào cuối những năm 1950 khi tìm kiếm các mô hình hình thức của cú pháp ngôn ngữ tự nhiên, và các tương ứng máy móc được thiết lập khi lý thuyết automaton phát triển qua những năm 1960, với các automaton bị chặn tuyến tính được Myhill giới thiệu và cấp độ nhạy ngữ cảnh được Kuroda làm rõ.

Key figures

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

Seminal works

• hopcroft2006
• sipser2013

Frequently asked questions

Bốn cấp độ của hệ thống phân cấp Chomsky là gì?

Từ yếu nhất đến mạnh nhất là ngôn ngữ chính quy (Loại 3), ngôn ngữ phi ngữ cảnh (Loại 2), ngôn ngữ nhạy ngữ cảnh (Loại 1) và ngôn ngữ đếm được đệ quy (Loại 0). Mỗi cấp độ nới lỏng các hạn chế về quy tắc ngữ pháp và tương ứng với một máy có nhiều bộ nhớ hơn.

Ngôn ngữ tự nhiên có được nắm bắt bởi hệ thống phân cấp Chomsky không?

Hệ thống phân cấp ban đầu được thúc đẩy bởi ngôn ngữ học, nhưng hầu hết các nhà ngôn ngữ học kết luận rằng ngôn ngữ tự nhiên không phải là phi ngữ cảnh, nằm ở một cấp độ thường được gọi là nhạy ngữ cảnh nhẹ. Hệ thống phân cấp vẫn là nền tảng trong khoa học máy tính mặc dù ngôn ngữ loài người chỉ phù hợp một cách lỏng lẻo.