Làm tất cả các biểu thức chính quy đều dừng lại?

Question

Có bất kỳ cụm từ thông dụng nào, đối với một số chuỗi đầu vào, hãy tìm kiếm kết quả phù hợp mãi mãi không?

Answer 1

Đối với một đầu vào hữu hạn, không có cụm từ thông dụng chính quy nào sẽ không dừng lại.

Bất kỳ cụm từ thông dụng chính thức nào cũng có thể được dịch sang một Automata hữu hạn xác định. Một DFA đọc đầu vào một ký tự tại một thời điểm, và, ở cuối đầu vào, bạn đang ở trạng thái chấp nhận hoặc ở trạng thái không chấp nhận. Nếu trạng thái đang chấp nhận, thì đầu vào khớp với biểu thức chính quy. Nếu không, nó không.

Hiện tại, hầu hết thư viện "biểu thức chính quy" hỗ trợ những thứ không phải là cụm từ thông dụng, chẳng hạn như tham chiếu ngược.Miễn là bạn tránh xa những tính năng đó, và có một đầu vào hữu hạn, bạn được đảm bảo tạm dừng. Nếu bạn không ... tùy thuộc vào chính xác những gì bạn đang sử dụng, bạn cũng có thể không được đảm bảo tạm dừng. Perl cho phép mã tùy ý được chèn vào, ví dụ, và mã tương đương, turing-máy tùy ý không được đảm bảo dừng lại.

Bây giờ, nếu đầu vào là vô hạn, sau đó biểu thức chính quy tầm thường có thể được tìm thấy mà sẽ không bao giờ dừng lại. Ví dụ: ".*".

Answer 2

Không theo nghĩa bạn mô tả, bạn có thể có một số cụm từ thông dụng rất kém hiệu quả chiếm nhiều tài nguyên và kết thúc là giết chết động cơ regex, điều này không giống như tạm dừng.

Tôi không nghĩ rằng tạm dừng thực sự áp dụng ở đây, vì những người bình luận khác của bài đăng này đã chỉ ra rất rõ ràng. http://en.wikipedia.org/wiki/Halting_problem

Answer 3

Theo this question, mọi biểu thức chính quy đều tạm dừng.

Answer 4

Tôi tưởng tượng, không thể tìm thấy cụm từ thông dụng không dừng lại.

Kích thước đầu vào của bạn là hữu hạn. Kích thước tối đa của bất kỳ nhóm con phù hợp nào của cụm từ thông dụng, ở mức tối đa, kích thước đầu vào của bạn.

Trừ khi thuật toán được sử dụng là khá ngu ngốc (đi qua các trường hợp nhiều lần), số lượng các nhóm con phù hợp, sẽ quá, là hữu hạn.

Vì vậy, nó sẽ dừng lại.

Answer 5

Tôi không thể tưởng tượng chuỗi đầu vào sẽ được phân tích cú pháp mãi mãi, mặc dù chuỗi dài vô hạn sẽ được phân tích cú pháp vĩnh viễn. Cho rằng một biểu thức chính quy có thể mô tả một ngôn ngữ thông thường, có khả năng là một tập hợp vô hạn các từ, sau đó một regex có thể mô tả một ngôn ngữ của các từ vô hạn, bao gồm các từ có độ dài vô hạn. Tuy nhiên, không có chuỗi đầu vào nào có thể dài vô hạn, do đó, tại một số điểm nó sẽ phải dừng lại.

Ví dụ: nếu * b được chấp nhận bằng ngôn ngữ và bạn có chuỗi dài 'a's', thì có, regex sẽ không bao giờ dừng lại. Thực tế, mặc dù, điều này là không thể.

Answer 6

regex chính thức thực sự là một phương pháp mô tả một automaton hữu hạn xác định để phân tích chuỗi. Các regex "phù hợp" nếu DFA gió lên trong một trạng thái chấp nhận ở phần cuối của đầu vào. Do DFA đọc tuần tự đầu vào của nó, nó sẽ luôn luôn dừng lại khi nó đến cuối đầu vào, và có hay không có một kết hợp chỉ là vấn đề kiểm tra trạng thái của DFA mà nó dừng ở đâu.

Kết hợp chuỗi con có hiệu quả giống nhau, ngoại trừ thay vì bị buộc dừng ở cuối chuỗi đọc, DFA sẽ bị buộc phải dừng sau khi đọc từng chuỗi con một lần - vẫn là trường hợp hữu hạn. (Có, hầu hết các công cụ regex thực hiện điều này theo cách tối ưu hơn một chút so với việc chỉ ném tất cả các chuỗi con có thể tại một DFA - nhưng về mặt khái niệm thì giới hạn đó vẫn còn ở đó).

Do đó, trường hợp duy nhất có thể mà DFA sẽ không dừng lại nếu đầu vào là vô hạn, thường được xem xét vượt quá phạm vi của sự cố dừng.

Answer 7

Có.

Cụm từ thông dụng có thể được biểu diễn bằng một máy trạng thái hữu hạn. Mỗi khi bạn nhận được một đầu vào nguyên tử, nó sẽ gây ra bất kỳ FSM được xác định rõ ràng nào để chuyển sang trạng thái đã biết.

Trường hợp ngoại lệ là khi bạn có đầu vào vô hạn, nhưng điều này không áp dụng được cho sự cố tạm dừng vì nó đề cập đến đầu vào hữu hạn. Khi bạn có một máy trạng thái hữu hạn và đầu vào hữu hạn, bạn luôn có thể xác định xem máy của bạn có dừng hay không.

http://en.wikipedia.org/wiki/Finite_state_machine

Answer 8

+1 cho câu trả lời của Daniel: tất cả các đầu vào hữu hạn gây ra đúng regex của (nghĩa là không phải backreferences hoặc các tính năng không regex khác) để ngăn chặn, và của regex là tương đương với DFAs.

Bonus: Regular Expression khớp có thể được đơn giản và nhanh (nhưng chậm trong Java, Perl, PHP, Python, Ruby, ...)

http://swtch.com/~rsc/regexp/regexp1.html

Lưu ý rằng hai đồ thị tại đầu bài viết có các tỷ lệ khác nhau trên trục y: một là giây, số còn lại là micro giây!