Giao điểm của hai biểu thức chính quy

Question

Im tìm kiếm hàm (PHP sẽ là tốt nhất), trả về true nếu chuỗi tồn tại khớp với cả regexpA và regexpB.

Ví dụ 1:

$regexpA = '[0-9]+'; 
$regexpB = '[0-9]{2,3}'; 

hasRegularsIntersection($regexpA,$regexpB) lợi nhuận TRUE vì '12' trận đấu cả hai regexps

Ví dụ 2:

$regexpA = '[0-9]+'; 
$regexpB = '[a-z]+'; 

hasRegularsIntersection($regexpA,$regexpB) trả về FALSE vì số không bao giờ phù hợp với literals.

Cảm ơn mọi đề xuất cách giải quyết vấn đề này.

Henry

Answer 1

Có thể. Tôi đã gặp nó một lần với lý do Pellet OWL trong khi học các công nghệ web ngữ nghĩa.

Here is an example cho biết cách biểu thức chính quy có thể được phân tích cú pháp thành cấu trúc cây. Sau đó bạn có thể (theo lý thuyết) phân tích hai biểu thức chính quy của bạn thành cây và xem liệu một cây có phải là một tập hợp con của cây khác không, tức là. nếu một cây có thể được tìm thấy trong các nút của cây khác.

Nếu nó được tìm thấy, thì cụm từ thông dụng khác sẽ khớp (không chỉ, mà còn) một tập con của cụm từ thông dụng đầu tiên sẽ khớp.

Nó không phải là một giải pháp, nhưng có lẽ nó sẽ giúp bạn.

Answer 2

Đối với biểu thức thông thường mà là thực sự thường xuyên (tức là không sử dụng các tính năng không thường xuyên như tài liệu tham khảo sau) bạn có thể làm như sau:

1. Chuyển đổi regexen vào automata hữu hạn (các thuật toán cho rằng có thể tìm thấy here (chương 9) chẳng hạn).
2. Xây dựng giao lộ của automata (Bạn có trạng thái cho mỗi trạng thái trong sản phẩm Descartes của các trạng thái của hai automata. Sau đó bạn chuyển đổi giữa các trạng thái theo các quy tắc chuyển đổi của tự động ban đầu. x1y2, bạn nhận được đầu vào a, automaton đầu tiên có chuyển đổi x1-> x4 cho đầu vào x và automaton thứ hai có y2-> y3, bạn chuyển sang trạng thái x4y3).
3. Kiểm tra xem có đường đi từ trạng thái bắt đầu đến trạng thái kết thúc trong ô tô mới hay không. Nếu có, hai regexen giao nhau, nếu không thì không.

Answer 3

Cụm từ thông dụng chỉ định một máy trạng thái hữu hạn có thể nhận ra một tập hợp chuỗi vô hạn tiềm ẩn. Tập hợp các chuỗi có thể là vô hạn nhưng số lượng các trạng thái phải là hữu hạn, vì vậy bạn có thể kiểm tra từng trạng thái một.

Lấy ví dụ thứ hai của bạn: Trong biểu thức đầu tiên, để chuyển từ trạng thái 0 sang trạng thái 1, chuỗi phải bắt đầu bằng một chữ số. Trong biểu thức thứ hai, để có được từ trạng thái 0 đến trạng thái 1, chuỗi phải bắt đầu bằng một chữ cái. Vì vậy, bạn biết rằng không có chuỗi nào sẽ đưa bạn từ trạng thái 0 đến trạng thái 1 trong cả hai biểu thức. Bạn có câu trả lời.

Lấy ví dụ đầu tiên: Bạn biết rằng nếu chuỗi bắt đầu bằng một chữ số bạn có thể lấy từ trạng thái 0 đến trạng thái 1 với biểu thức chính quy.Vì vậy, bây giờ bạn có thể loại bỏ trạng thái 0 cho mỗi cái, và chỉ trả lời câu hỏi cho mỗi một trong hai trạng thái hữu hạn (hiện tại một trạng thái nhỏ hơn).

Điều này trông rất giống với "sự cố tạm dừng" nổi tiếng, như bạn biết là không thể giải quyết trong trường hợp chung cho máy Turing hoặc tương đương. Nhưng trên thực tế, vấn đề dừng lại là khả năng giải được cho một máy hữu hạn, đơn giản vì có một số hữu hạn các trạng thái.

Tôi tin rằng bạn có thể giải quyết vấn đề này với FSM không xác định. Nếu regex của bạn chỉ có một sự chuyển tiếp từ mỗi trạng thái sang trạng thái tiếp theo, một FSM xác định có thể giải quyết nó. Nhưng một biểu thức chính quy có nghĩa là ví dụ nếu bạn đang ở trong tiểu bang 2, thì nếu caracter là một chữ số bạn đi đến tiểu bang 3, nếu nhân vật là một lá thư bạn đến tiểu bang 4.

Vì vậy, đây là những gì tôi sẽ làm:

1. Giải quyết nó cho tập con của FSM chỉ có một chuyển tiếp từ trạng thái này sang trạng thái tiếp theo. Ví dụ: regex khớp với cả "Bob" và "bob" và regex thứ hai chỉ khớp với "bob" và "boB".

2. Xem bạn có thể triển khai giải pháp trong máy trạng thái hữu hạn hay không. Tôi nghĩ điều này có thể xảy ra. Đầu vào cho một trạng thái là một cặp biểu diễn một quá trình chuyển đổi cho một FSM và một quá trình chuyển đổi cho một FSM thứ hai. Ví dụ: Trạng thái 0: Nếu (r1, r2) là (("B" hoặc "b"), "b") thì Trạng thái 1. Trạng thái 1: Nếu (r1, r2) là (("o"), ("o")) sau đó là trạng thái 2. v.v.

3. Bây giờ cho trường hợp tổng quát hơn, trong trường hợp ví dụ, hai trạng thái trở lại trạng thái hai hoặc trạng thái trước đó; ví dụ, regex 1 chỉ nhận ra "đáp ứng" nhưng regex 2 nhận ra "meeeet" với số lượng không giới hạn của e. Bạn sẽ phải giảm bớt chúng để regex 1 nhận ra "t" và regex 2 nhận ra "t". Tôi nghĩ rằng điều này có thể được giải quyết bằng FSM không xác định.

Đó là trực giác của tôi.

Tôi không nghĩ rằng nó hoàn thành NP, chỉ vì trực giác của tôi cho tôi biết bạn sẽ có thể rút ngắn từng regex theo một trạng thái với mỗi bước.

Answer 4

Theory.

Java library.

Cách sử dụng:

/** 
* @return true if the two regexes will never both match a given string 
*/ 
public boolean isRegexOrthogonal(String regex1, String regex2) { 
    Automaton automaton1 = new RegExp(regex1).toAutomaton(); 
    Automaton automaton2 = new RegExp(regex2).toAutomaton(); 
    return automaton1.intersection(automaton2).isEmpty(); 
}