Làm thế nào để chứng minh một ngôn ngữ không phải là chính quy?

Công cụ phổ biến nhất là bổ đề bơm, nói rằng mọi chuỗi đủ dài trong một ngôn ngữ chính quy đều chứa một chuỗi con có thể được lặp lại bất kỳ số lần nào mà vẫn nằm trong ngôn ngữ đó. Việc tìm một chuỗi không thể bơm theo cách này chứng minh ngôn ngữ đó không phải là chính quy; định lý Myhill–Nerode đưa ra một lập luận thay thế bằng cách chỉ ra vô số tiền tố có thể phân biệt được.

Nếu tự động không xác định không mạnh hơn, tại sao lại sử dụng chúng?

Chúng thường nhỏ hơn nhiều và dễ thiết kế hoặc suy ra từ một biểu thức chính quy. Phép xây dựng tập con có thể chuyển đổi chúng sang dạng xác định khi cần, với chi phí tiềm năng theo cấp số mũ về số lượng trạng thái, vì vậy tính không xác định là một công cụ đặc tả tiện lợi hơn là một sự gia tăng về sức mạnh nhận dạng.

Tự động hữu hạn và Ngôn ngữ chính quy

Tự động hữu hạn là những máy tính đơn giản nhất, đọc đầu vào từng ký hiệu một chỉ sử dụng một số lượng hữu hạn các trạng thái bên trong, và các ngôn ngữ mà chúng nhận dạng chính xác là các ngôn ngữ chính quy.

Tìm chủ đề với PaperMindSắp ra mắtFind papers & topics

Tools & resources

Tải xuống bản trình chiếu

Learn & explore

VideoSắp ra mắt

Definition

Một tự động hữu hạn là một máy có một tập hợp hữu hạn các trạng thái, một hàm chuyển đổi trên các ký hiệu đầu vào, một trạng thái bắt đầu và các trạng thái chấp nhận; nó chấp nhận một chuỗi nếu việc đọc chuỗi đó đưa nó từ trạng thái bắt đầu vào một trạng thái chấp nhận, và tập hợp các chuỗi được chấp nhận là ngôn ngữ của nó.

Scope

Chủ đề này bao gồm tự động hữu hạn xác định và không xác định, sự tương đương của chúng thông qua phép xây dựng tập con, biểu thức chính quy và định lý Kleene, định lý Myhill–Nerode và tối thiểu hóa trạng thái, các tính chất đóng của ngôn ngữ chính quy, và bổ đề bơm được sử dụng để chứng minh rằng một số ngôn ngữ nhất định không phải là chính quy.

Core questions

Những ngôn ngữ nào có thể được nhận dạng chỉ bằng một lượng bộ nhớ cố định, hữu hạn?
Tại sao tự động hữu hạn xác định và không xác định lại có sức mạnh tương đương?
Làm thế nào để chứng minh rằng một ngôn ngữ cụ thể không phải là chính quy?
Tự động nhỏ nhất nhận dạng một ngôn ngữ chính quy cho trước là gì?

Key theories

Phép xây dựng tập con: Bất kỳ tự động hữu hạn không xác định nào cũng có thể được mô phỏng bởi một tự động xác định mà các trạng thái của nó là các tập hợp của các trạng thái ban đầu, chứng minh rằng hai mô hình nhận dạng chính xác cùng một ngôn ngữ.
Định lý Kleene: Một ngôn ngữ được nhận dạng bởi một tự động hữu hạn nếu và chỉ nếu nó được mô tả bởi một biểu thức chính quy, thiết lập sự tương đương giữa mô tả máy và mô tả đại số của các ngôn ngữ chính quy.
Định lý Myhill–Nerode: Một ngôn ngữ là chính quy chính xác khi quan hệ không thể phân biệt chuỗi của nó có hữu hạn lớp, và các lớp này xác định tự động xác định tối thiểu duy nhất cho ngôn ngữ đó.

Clinical relevance

Tự động hữu hạn là động cơ đằng sau việc khớp biểu thức chính quy, các bộ quét và phân tích từ vựng trong trình biên dịch, tìm kiếm và thay thế trong trình soạn thảo văn bản, và phát hiện mẫu trong các hệ thống xâm nhập mạng, nơi nhận dạng bộ nhớ giới hạn giúp xử lý nhanh chóng và có thể dự đoán được.

History

Dựa trên mô hình mạng thần kinh của McCulloch và Pitts năm 1943, Kleene đã mô tả các sự kiện mà tự động hữu hạn có thể biểu diễn vào khoảng năm 1951, và Rabin cùng Scott đã hình thức hóa tự động không xác định và các vấn đề quyết định của chúng vào năm 1959, công trình sau này được công nhận với Giải thưởng Turing.

Key figures

Stephen Kleene
Michael Rabin
Dana Scott
Anil Nerode

Seminal works

rabinScott1959
sipser2013

Frequently asked questions

Làm thế nào để chứng minh một ngôn ngữ không phải là chính quy?: Công cụ phổ biến nhất là bổ đề bơm, nói rằng mọi chuỗi đủ dài trong một ngôn ngữ chính quy đều chứa một chuỗi con có thể được lặp lại bất kỳ số lần nào mà vẫn nằm trong ngôn ngữ đó. Việc tìm một chuỗi không thể bơm theo cách này chứng minh ngôn ngữ đó không phải là chính quy; định lý Myhill–Nerode đưa ra một lập luận thay thế bằng cách chỉ ra vô số tiền tố có thể phân biệt được.
Nếu tự động không xác định không mạnh hơn, tại sao lại sử dụng chúng?: Chúng thường nhỏ hơn nhiều và dễ thiết kế hoặc suy ra từ một biểu thức chính quy. Phép xây dựng tập con có thể chuyển đổi chúng sang dạng xác định khi cần, với chi phí tiềm năng theo cấp số mũ về số lượng trạng thái, vì vậy tính không xác định là một công cụ đặc tả tiện lợi hơn là một sự gia tăng về sức mạnh nhận dạng.