Để truy cập trực tiếp vào câu hỏi của bạn, bạn nên thực hiện một nghiên cứu ngắn về số Chomsky Hierarchy. Đây là một cách cũ và xinh đẹp để tổ chức các ngôn ngữ chính thức trong các bộ tăng độ phức tạp. Các bậc thấp nhất của hệ thống phân cấp là các ngôn ngữ thông thường. Bạn có thể đoán - và bạn sẽ đúng - RL là chính xác những biểu tượng có thể được biểu diễn bằng cụm từ thông dụng "thuần túy": Chỉ có bảng chữ cái, chuỗi rỗng, nối, xoay vòng |, và sao Kleene * (nhìn Ma, không có tham khảo ngược). Một định lý cổ điển của lý thuyết ngôn ngữ chính thức - Định lý Kleene - là DFA, NFA (như được mô tả trong bài báo bạn trích dẫn), và các biểu thức chính quy đều có chính xác là cùng sức mạnh để thể hiện và nhận biết ngôn ngữ. Cấu trúc của Thompson được đưa ra trong bài viết là một phần của bằng chứng của định lý.
Mỗi RL cũng là một CFL. Nhưng có vô số CFL không thường xuyên. Một tính năng có thể tồn tại trong CFL làm cho chúng quá phức tạp để được thường xuyên là các cặp cân bằng của sự vật: dấu ngoặc đơn, khối đầu tiên, vv Gần như tất cả các ngôn ngữ lập trình đều là CFL. CFL có thể được nhận diện hiệu quả bởi những gì được gọi là tự động đẩy xuống Bản chất này là một NFA với một ngăn xếp được dán trên. Ngăn xếp phát triển lớn đến mức cần thiết, vì vậy nó không còn là một automaton hữu hạn nữa. Phân tích cú pháp của các ngôn ngữ lập trình thực là gần như tất cả các biến thể trên tự động đẩy xuống.
Cân nhắc regex với backreference
^(b*a)\1$
Nói cách, điều này thể hiện chuỗi có độ dài 2n đối với một số n, nơi mà cả n'th và các nhân vật 2n'th là a và tất cả các nhân vật khác là b. Đây là một ví dụ hoàn hảo về một CFL không thường xuyên. Bạn có thể chứng minh một cách chặt chẽ điều này với một công cụ ngôn ngữ chính thức khác được gọi là bổ đề bơm.
Đây chính xác là lý do khiến tài liệu tham khảo trở lại gây ra vấn đề! Chúng cho phép "cụm từ thông dụng" đại diện cho các ngôn ngữ không thường xuyên. Do đó không có NFA hoặc DFA nào có thể nhận ra chúng.
Nhưng chờ đã, thậm chí còn tồi tệ hơn tôi đã thực hiện cho đến nay. Cân nhắc
^(b*a)\1\1$
Bây giờ chúng ta có một chuỗi có độ dài 3n nơi n'th, 2n'th, và các yếu tố 3n'th là a và tất cả những người khác b. Có một hương vị khác của bổ đề bơm cho phép một bằng chứng rằng ngôn ngữ này thậm chí còn quá phức tạp để trở thành một CFL! Không có động cơ đẩy xuống có thể nhận ra điều này.
Quay lại tham chiếu cho phép các regexes tăng áp này đại diện cho các ngôn ngữ có ba bậc lên Hệ thống phân cấp Chomsky: Ngôn ngữ nhạy cảm theo ngữ cảnh. Nói một cách tổng quát, cách duy nhất để nhận diện CSL là kiểm tra tất cả các chuỗi trong ngôn ngữ có độ dài bằng nhau (ít nhất là nếu P! = NP, nhưng điều đó đúng cho tất cả các mục đích thực tế và một câu chuyện hoàn toàn khác). Số lượng các chuỗi như vậy là số mũ theo độ dài của chuỗi bạn đang so khớp.
Đây là lý do tại sao trình tìm kiếm regex tìm kiếm là cần thiết. Bạn có thể rất thông minh theo cách bạn thiết kế tìm kiếm. Nhưng sẽ luôn có một số đầu vào làm cho nó mất thời gian.
Vì vậy, tôi đồng ý với tác giả của bài báo bạn đã trích dẫn. Có thể viết các biểu thức hoàn toàn ngây thơ với không có phản hồi sẽ được nhận diện hiệu quả cho gần như tất cả các đầu vào, nhưng ở đó có một số đầu vào gây ra đối sánh regex Perl hoặc Java hoặc Python - vì nó là tìm kiếm ngược hàng triệu năm để hoàn thành trận đấu. Điều này là điên. Bạn có thể có một kịch bản chính xác và hoạt động tốt trong nhiều năm và sau đó khóa một ngày chỉ vì nó vấp vào một trong những đầu vào xấu. Giả sử regex được chôn cất trong phân tích cú pháp thông điệp của hệ thống định vị trong máy bay bạn đang cưỡi ...
Sửa
Bằng cách yêu cầu, tôi sẽ phác thảo cách bổ đề bơm có thể được sử dụng để chứng minh ngôn ngữ a^k b a^k b không thường xuyên. Ở đây a^k là viết tắt của a lặp lại k lần. PL nói rằng phải tồn tại một số nguyên dương N sao cho mỗi chuỗi trong một ngôn ngữ thông thường có độ dài ít nhất là N phải có dạng R S T sao cho R S^k T cũng có trong ngôn ngữ cho tất cả k tự nhiên. Tại đây R, S, T là các chuỗi và S không được để trống.
Chứng minh PL phụ thuộc vào thực tế là mọi ngôn ngữ thông thường đều tương ứng với một số DFA. Một đầu vào được chấp nhận cho DFA này dài hơn số trạng thái của nó (tương đương với L trong bổ đề) phải làm cho nó thành "vòng lặp": để lặp lại trạng thái. Gọi trạng thái này X. Máy tiêu thụ một số chuỗi R để có được từ đầu đến X, sau đó S để lặp lại X, sau đó T để đến trạng thái chấp nhận.Ngoài ra, việc thêm các bản sao S (hoặc xóa S) khác vào đầu vào chỉ tương ứng với một số "vòng lặp" khác nhau từ X trở lại X. Do đó, chuỗi mới với các bản sao S bổ sung (hoặc đã xóa) cũng sẽ được chấp nhận .
Kể từ mỗi RL phải đáp ứng PL, bằng chứng cho thấy ngôn ngữ không được tiến hành thường xuyên bằng cách cho thấy rằng ngôn ngữ đó không mâu thuẫn với PL. Đối với ngôn ngữ của chúng tôi, điều này không khó. Giả sử bạn đang cố gắng thuyết phục tôi ngôn ngữ L = a^k b a^k b thỏa mãn PL. Bởi vì nó làm như vậy, bạn phải có khả năng cho tôi một số giá trị của N (xem ở trên): số lượng các trạng thái trong một DFA giả định nhận ra L. Tại thời điểm đó, tôi sẽ nói, "Được rồi Mr. Regular Guy, hãy xem xét chuỗi B = a^N b a^N b. " Nếu L là thông thường, B phải làm cho DFA này (không có vấn đề gì) giống như vòng lặp trong N ký tự đầu tiên, mà phải là tất cả a s! Vì vậy, vòng lặp (chuỗi S ở trên) bao gồm tất cả a s, cũng vậy. Với điều này tôi có thể ngay lập tức cho thấy rằng yêu cầu của bạn về L là thường xuyên là sai. Tôi chỉ chọn đi vòng quanh lần thứ hai. Điều này sẽ làm cho DFA giả định này của bạn chấp nhận một chuỗi mới a^M b a^N b, trong đó M> N vì tôi đã thêm a s vào nửa đầu của nó. Ouch! Chuỗi mới này không có trong L, vì vậy PL không đúng sau tất cả. Vì tôi có thể thực hiện thủ thuật này mỗi lần bất kể N bạn cung cấp, PL không thể giữ cho L, và L không thể là bình thường sau tất cả.
Vì không thường xuyên, định lý của Kleene cho chúng ta biết không có DFA hay FA cũng không phải là regex "thuần túy" mô tả nó.
Bằng chứng cho phép quay lại cho phép các ngôn ngữ không có ngữ cảnh tự do có vòng tương tự nhưng cần nền trên tự động đẩy xuống mà tôi sẽ không cung cấp ở đây. Google sẽ cung cấp.
NB: Cả hai trường hợp này đều thiếu bằng chứng cho thấy các tham chiếu ngược giúp NP nhận diện hoàn chỉnh. Họ chỉ đơn thuần nói một cách rất nghiêm ngặt rằng việc tái tạo lại thêm sự phức tạp thực sự vào các biểu thức thông thường thuần túy. Chúng cho phép các ngôn ngữ không thể nhận ra với bất kỳ máy nào có bộ nhớ hữu hạn, cũng như không có bất kỳ bộ nhớ LIFO vô hạn nào. Tôi sẽ để NP hoàn chỉnh bằng chứng cho người khác.
Bài viết loại câu trả lời ngay tại đó, regex với backrefs là nó không phải là một biểu thức chính quy, bởi đó là định nghĩa chính thức. Altho điều này không trả lời tại sao một thuật toán nhanh như vậy không thể được thực hiện cho một regex với backrefs. – Qtax