Lý thuyết Ngôn ngữ Hình thức và Automata

Lý thuyết về các ngôn ngữ hình thức và các máy trừu tượng nhận dạng chúng, cung cấp từ vựng để mô tả mức độ phức tạp của một mẫu ngôn ngữ và những thuật toán nào có thể xử lý nó.

Definition

Lý thuyết ngôn ngữ hình thức nghiên cứu các tập hợp chuỗi được định nghĩa bởi ngữ pháp, và lý thuyết automata nghiên cứu các máy trừu tượng quyết định tư cách thành viên trong các tập hợp đó.

Scope

Bao gồm hệ thống phân cấp Chomsky (ngôn ngữ chính quy, phi ngữ cảnh, ngữ cảnh, đệ quy liệt kê được), các ngữ pháp tương ứng và các automata nhận dạng – máy trạng thái hữu hạn, automata đẩy xuống và máy Turing. Nó đề cập đến các thuộc tính đóng và tính quyết định liên quan đến xử lý ngôn ngữ và câu hỏi về vị trí của ngôn ngữ tự nhiên trong hệ thống phân cấp. Các bổ đề bơm và các bằng chứng phức tạp đầy đủ được coi là nội dung nền tảng hơn là nội dung chính.

Core questions

• Automaton nào tương ứng với mỗi cấp độ của hệ thống phân cấp Chomsky?
• Ngôn ngữ tự nhiên nằm ở đâu trong hệ thống phân cấp, và tại sao nó được cho là vượt quá sức mạnh phi ngữ cảnh?
• Một lớp ngôn ngữ được đóng dưới một phép toán có nghĩa là gì, và tại sao điều đó lại quan trọng đối với kỹ thuật?

Key concepts

• ngôn ngữ chính quy
• ngữ pháp phi ngữ cảnh
• ngữ pháp ngữ cảnh
• automaton trạng thái hữu hạn
• automaton đẩy xuống
• máy Turing
• thuộc tính đóng
• tính ngữ cảnh yếu

Key theories

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

Bốn lớp ngôn ngữ hình thức lồng nhau, mỗi lớp được tạo ra bởi một loại ngữ pháp hạn chế và được nhận dạng bởi một automaton tương ứng, sắp xếp các cấu trúc ngôn ngữ theo sức mạnh tính toán cần thiết.

Sự tương ứng ngữ pháp–automaton

Mỗi lớp ngữ pháp được chứng minh là tương đương với một lớp máy – ngữ pháp chính quy với automata hữu hạn, ngữ pháp phi ngữ cảnh với automata đẩy xuống – liên kết các mô tả tạo sinh với các thuật toán nhận dạng.

History

Bài báo năm 1956 của Chomsky đã giới thiệu hệ thống phân cấp như một phần của lập luận rằng các mô hình trạng thái hữu hạn không đủ cho ngôn ngữ tự nhiên. Các thập kỷ sau đó đã hình thức hóa các tương ứng automata, và các nhà ngôn ngữ học tính toán sau này đã chỉ ra rằng ngôn ngữ tự nhiên yêu cầu sức mạnh 'ngữ cảnh yếu' tối đa, thúc đẩy các hình thức ngữ pháp vượt ra ngoài ngữ pháp phi ngữ cảnh.

Debates

Ngôn ngữ tự nhiên có phải là phi ngữ cảnh không?

Các phụ thuộc chéo trong các ngôn ngữ như tiếng Đức Thụy Sĩ đã được sử dụng để lập luận rằng ngôn ngữ tự nhiên vượt quá sức mạnh phi ngữ cảnh, dẫn đến khái niệm tính ngữ cảnh yếu như là mức độ biểu cảm phù hợp.

Key figures

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

Seminal works

• chomsky1956
• hopcroft2006

Frequently asked questions

Sự khác biệt giữa ngôn ngữ chính quy và ngôn ngữ phi ngữ cảnh là gì?

Ngôn ngữ chính quy có thể được nhận dạng bằng bộ nhớ hữu hạn bởi một automaton trạng thái hữu hạn; ngôn ngữ phi ngữ cảnh có thể yêu cầu một ngăn xếp (một automaton đẩy xuống) để theo dõi cấu trúc lồng nhau, chẳng hạn như dấu ngoặc đơn cân bằng hoặc các mệnh đề nhúng.