8
Có thể kiểm tra xem cụm từ thông dụng nhất định có khớp với bất kỳ chuỗi nào không? Cụ thể, tôi đang tìm hàm matchesEverything($regex) trả về true iff $regex sẽ khớp với bất kỳ chuỗi nào.Kiểm tra xem một regex nhất định có khớp với bất kỳ thứ gì
Tôi cho rằng điều này tương đương với yêu cầu, "được cung cấp một regex r, không tồn tại một chuỗi không khớp với r?" và tôi không nghĩ rằng đây là giải pháp mà không đặt giới hạn trên tập hợp của "tất cả các chuỗi". Tức là, nếu tôi cho rằng các chuỗi sẽ không bao giờ chứa "blahblah", thì tôi có thể chỉ cần kiểm tra xem r có khớp với "blahblah" hay không. Nhưng nếu không có giới hạn như vậy thì sao? Tôi tự hỏi nếu vấn đề này có thể được giải quyết kiểm tra nếu regex r là tương đương với .*.
Tôi tin rằng điều này tương đương với [Sự cố tạm dừng] (http://en.wikipedia.org/wiki/Halting_problem). Không thể viết một thuật toán để xác định xem một regex tùy ý có tương đương với '. *' –
Regexes với các thuật toán và backrefs, nhưng không có nội suy mã, phải là một tập hợp con hoặc bằng ngữ pháp nhạy cảm ngữ cảnh. Quyết định các ngôn ngữ này không hoàn toàn Turing, do đó câu hỏi này không nên tương đương với vấn đề dừng. * Nếu *, cho một CSG, chúng ta có thể tạo ra một chuỗi ngôn ngữ này bằng cách thay thế các quy tắc, sau đó chúng ta có thể áp dụng một sự thay thế bị cấm, do đó tạo ra một chuỗi không có trong ngôn ngữ của chúng ta. Đáng buồn là tôi không biết liệu đây có phải là trường hợp không, và tôi sẽ không thể phác họa bằng chứng về điều này. – amon
Điều này được gọi là "Vấn đề trống rỗng", và có thể giải quyết được cho DFA/NFA (tức là các regex không có phản hồi/giải đáp) http://www.cs.miami.edu/~ogihara/csc527/new04-1.pdf Đối với regexes với backrefs (ngữ pháp nhạy cảm ngữ pháp), vấn đề trống rỗng là undecidable.(Tôi không thể tìm thấy một bằng chứng ngay bây giờ, nhưng nó thường được đề cập trong văn học) – rmmh