Automata và Ngôn ngữ Hình thức
Lý thuyết automata và ngôn ngữ hình thức nghiên cứu các máy móc lý tưởng hóa với sức mạnh ngày càng tăng và các lớp chuỗi, hay ngôn ngữ, mà mỗi máy có thể nhận dạng, đưa ra một mô tả toán học chính xác về những gì được coi là một mẫu và những gì cần thiết để phát hiện một mẫu.
Definition
Một ngôn ngữ hình thức là một tập hợp các chuỗi hữu hạn trên một bảng chữ cái cố định, và một automaton là một thiết bị tính toán trừu tượng mà các phép tính chấp nhận của nó định nghĩa một ngôn ngữ như vậy; lĩnh vực này phân loại các ngôn ngữ theo loại automaton hoặc ngữ pháp đơn giản nhất tạo ra hoặc nhận dạng chúng.
Scope
Lĩnh vực này bao gồm automata hữu hạn và ngôn ngữ chính quy, automata đẩy xuống và ngôn ngữ phi ngữ cảnh, hệ thống phân cấp Chomsky liên hệ ngữ pháp với các mô hình máy, các thuộc tính đóng và quyết định của các lớp ngôn ngữ, và automata xử lý các từ và cây vô hạn, cùng với các đặc trưng đại số và logic đi kèm.
Sub-topics
Core questions
- Những ngôn ngữ nào mà một máy có bộ nhớ hữu hạn có thể nhận dạng, và những ngôn ngữ nào không thể nhận dạng?
- Ngữ pháp và các mô hình máy tương ứng như thế nào qua các cấp độ của hệ thống phân cấp Chomsky?
- Những câu hỏi nào về một lớp ngôn ngữ, chẳng hạn như tính rỗng hay tính tương đương, có thể quyết định được bằng thuật toán?
- Automata mở rộng sang các từ và cây vô hạn như thế nào, và tại sao điều này lại quan trọng đối với việc xác minh?
Key theories
- Sự tương đương giữa automata hữu hạn xác định và không xác định
- Mọi automaton hữu hạn không xác định đều có thể được chuyển đổi bằng cách xây dựng tập con thành một automaton xác định chấp nhận cùng một ngôn ngữ, do đó tính không xác định không làm tăng sức mạnh nhận dạng ở cấp độ trạng thái hữu hạn mặc dù nó có thể ngắn gọn hơn theo cấp số nhân.
- Định lý Kleene
- Các ngôn ngữ được nhận dạng bởi automata hữu hạn chính xác là các ngôn ngữ chính quy được mô tả bởi các biểu thức chính quy, liên kết các quan điểm máy, đại số và ngữ pháp của lớp ngôn ngữ đơn giản nhất.
- Hệ thống phân cấp Chomsky
- Các ngôn ngữ chính quy, phi ngữ cảnh, ngữ cảnh và đệ quy đếm được tạo thành một chuỗi bao hàm nghiêm ngặt, mỗi cấp độ được khớp với một loại ngữ pháp và một mô hình automaton có cấu trúc bộ nhớ tương ứng.
Clinical relevance
Automata hữu hạn và biểu thức chính quy cung cấp sức mạnh cho phân tích từ vựng trong trình biên dịch, tìm kiếm văn bản và đặc tả giao thức, trong khi ngữ pháp phi ngữ cảnh là nền tảng cho việc phân tích cú pháp ngôn ngữ lập trình; automata trên các đối tượng vô hạn tạo thành cốt lõi thuật toán của kiểm tra mô hình (model checking), nơi một hệ thống được xác minh dựa trên một đặc tả logic thời gian.
History
Các mô hình trạng thái hữu hạn xuất hiện từ mạng lưới thần kinh của McCulloch và Pitts vào những năm 1940 và được Kleene đưa ra dạng lý thuyết ngôn ngữ vào khoảng năm 1951. Rabin và Scott đã giới thiệu automata không xác định vào năm 1959, trong khi ngữ pháp của Chomsky từ cuối những năm 1950 đã tổ chức các lớp ngôn ngữ thành hệ thống phân cấp vẫn còn cấu trúc chủ đề này.
Key figures
- Stephen Kleene
- Michael Rabin
- Dana Scott
- Noam Chomsky
Related topics
Seminal works
- rabinScott1959
- sipser2013
- hopcroft2006
Frequently asked questions
- Tại sao một automaton hữu hạn không thể nhận dạng các dấu ngoặc đơn cân bằng?
- Việc nhận dạng các lồng ghép sâu tùy ý đòi hỏi phải đếm số lượng dấu mở ngoặc vẫn chưa được khớp, điều này có thể vượt quá bất kỳ số trạng thái cố định nào. Một automaton hữu hạn chỉ có bộ nhớ giới hạn, vì vậy khả năng đếm này nằm ở cấp độ cao hơn, với automata đẩy xuống và ngôn ngữ phi ngữ cảnh.
- Lợi ích thực tế của lý thuyết ngôn ngữ hình thức là gì?
- Nó cho các kỹ sư biết những mẫu nào mà một công cụ nhất định có thể thể hiện. Biểu thức chính quy đủ cho các mã thông báo nhưng không đủ cho cấu trúc lồng ghép, đó là lý do tại sao các trình biên dịch chia công việc giữa một bộ phân tích từ vựng chính quy và một bộ phân tích cú pháp phi ngữ cảnh, và tại sao các công cụ xác minh dựa vào automata trên các từ vô hạn.