Thuật toán tồn tại có thể xác định xem một ngôn ngữ thông thường có khớp với bất kỳ đầu vào nào mà một ngôn ngữ thông thường khác khớp không?

Question

Hãy nói rằng chúng ta có biểu thức thông thường:..

• Xin chào W. * rld
• Hello World
• * Thế Giới
• * W. *

Tôi muốn giảm thiểu số lượng các regex được yêu cầu để khớp với đầu vào tùy ý.

Để làm điều đó, tôi cần phải tìm hiểu xem một biểu thức chính quy có khớp với bất kỳ đầu vào nào khớp với một biểu thức khác hay không. Điều đó có thể không?

Billy3

Answer 1

Mọi biểu thức chính quy đều có thể liên kết với DFA - bạn có thể giảm thiểu DFA và vì biểu mẫu tối thiểu là duy nhất, bạn có thể quyết định xem hai biểu thức có tương đương hay không. Dani Cricco chỉ ra thuật toán Hopcroft O (n log n). Có một thuật toán cải tiến khác của Hopcroft và Craft, nó kiểm tra sự tương đương của hai DFA trong O (n).

Để có một khảo sát tốt về vấn đề này và một cách tiếp cận thú vị cho vấn đề này, tôi khuyên bạn nên xem lại bài báo Testing the Equivalence of Regular Languages, từ arXiv.

Chỉnh sửa sau: nếu bạn quan tâm đến việc đưa vào thay vì tương đương với cụm từ thông dụng, tôi đã xem một bài báo có thể quan tâm: Inclusion Problem for Regular Expressions - Tôi chỉ lướt qua nó nhưng dường như có chứa thuật toán thời gian đa thức vấn đề.

Answer 2

Có.

Vấn đề tương đương với hai ngôn ngữ thông thường là có thể giải quyết được.

Phác thảo của một thuật toán:

• giảm thiểu cả hai séc DFAs
• nếu họ isomorph

Answer 3

chắc !. Một biểu thức chính quy có thể được biểu diễn như một FSM (Máy trạng thái hữu hạn) và có số lượng FSM vô hạn có thể nhận ra cùng một chuỗi.

Isomorphism là tên mô tả nếu hai FSM là tương đương. Có một vài thuật toán để giảm thiểu FSM. Ví dụ: Hopcroft minimization algorithm có thể giảm thiểu tối đa hai FSM trong O (n log n), trên một automaton trạng thái n.

Answer 4

Vấn đề này được gọi là "bao gồm" hoặc "subsumption" của biểu thức chính quy, vì những gì bạn đang yêu cầu, là liệu tập hợp các từ phù hợp với một regexp bao gồm (hoặc subsumes) tập hợp các từ phù hợp với regex khác . Bình đẳng là một câu hỏi khác thường thường có nghĩa là hai regexps có khớp chính xác với cùng một từ hay không, tức là chúng tương đương về mặt chức năng. Ví dụ "a *" bao gồm "aa *", trong khi chúng không bằng nhau.

Tất cả các thuật toán đã biết để bao gồm regexp là trường hợp xấu nhất mất thời gian theo cấp số mũ trong kích thước của regexp.Tuy nhiên, thuật toán tiêu chuẩn là như thế này:

Input r1 và r2 Output Yes nếu r1 bao gồm r2

1. Tạo DFA (r1) và DFA (r2)
2. Tạo Neg (DFA (r1)) (khớp chính xác với những từ r1 không khớp)
3. Tạo Neg (DFA (r1)) x DFA (r2) (khớp chính xác với những từ khớp với Neg (DFA (r1)) và DFA (r2))
4. Kiểm tra xem automaton được tạo trong 3. không khớp với bất kỳ từ nào

Tác phẩm này, vì những gì bạn đang kiểm tra là không có từ nào khớp với r2 không khớp với r1.