Określanie, czy wyrażenie regularne jest podzbiorem innego

Question

Mam dużą kolekcję wyrażeń regularnych, które po dopasowaniu wywołują określony program obsługi http. Niektóre z starszych wyrażeń regularnych są niedostępne (na przykład a.c* ⊃ abc*) i chciałbym je przyciąć.

Czy istnieje biblioteka, która z dwóch regexów powie mi, czy druga jest podzbiorem pierwszej?

Nie byłem pewien, czy na początku było to rozstrzygające (pachniało jak problem zatrzymania pod inną nazwą). Ale okazuje się, że jest to it's decidable.

Answer 1

Istnieje odpowiedź w sekcji dotyczącej matematyki: https://math.stackexchange.com/questions/283838/is-one-regular-language-subset-of-another.

podstawowa idea:

• Oblicz minimalny DFA dla obu językach.
• Oblicz iloczyn iloczynów obu automatów M1 i M2, co oznacza, że ​​każdy stan składa się z pary [m1, m2], gdzie m1 pochodzi z M1, a m2 z M2 dla wszystkich możliwych kombinacji.
• Nowe przejście F12 to: F12 ([m1, m2], x) => [F1 (m1, x), F2 (m2, x)]. Oznacza to, że jeśli nastąpiło przejście w M1 ze stanu m1 do m1 'podczas odczytu x oraz w M2 ze stanu m2 do m2' podczas odczytu x, to istnieje jedno przejście w M12 z [m1, m2] do [m1 ', m2' ] podczas czytania x.
• Pod koniec zajrzeć do osiągalnych stanów:
  • Jeśli jest para [przyjmując, odrzucając] wtedy M2 nie jest podzbiorem M1
  • Jeśli jest para [odrzucając accapting] następnie M1 nie jest podzbiorem M2

byłoby benificial gdyby po prostu obliczyć nowe przejścia i wynikające stany, pomijając wszystkie stany osiągalne niż od początku.

Answer 2

Trying to find the complexity of this problem lead me to this paper.

formalnej identyfikacji problemu można znaleźć w: jest to zwykle nazywane problem włączenie

Problem włączenie do R, jest sprawdzenie, Z dwóch wyrażeń Rt r '∈ R, , czy r ⊆ r'.

że papier ma kilka świetnych informacji (Podsumowanie: wszystko ale najprostszych wyrażeń są dość skomplikowane), jednak poszukiwania informacji na temat problemu integracji wiedzie bezpośrednio z powrotem do StackOverflow. Ta odpowiedź miała już link do a paper describing a passable polynomial time algorithm, który powinien obejmować wiele typowych przypadków.

Answer 3

Jeśli wyrażenia regularne używają "zaawansowanych funkcji" typowych masek procesowych (takich jak w językach Perl, Java, Python, Ruby itp.), Które umożliwiają akceptowanie języków, które nie są regularne, oznacza to, że nie masz szczęścia. Problem jest ogólnie nierozstrzygalny. Na przykład. problem polegający na tym, czy jeden automat wrzutowy rozpoznaje ten sam język wolny od kontekstu (CF), co inny, który jest nierozstrzygalny. Rozszerzone wyrażenia regularne mogą opisywać języki CF.

Z drugiej strony, jeśli wyrażenia regularne są "prawdziwe" w sensie teoretycznym, składające się tylko z konkatenacji, naprzemienności i gwiazdy Kleene nad ciągami z skończonym alfabetem oraz zwykłym cukrem syntaktycznym na tych (klasach znaków, +,?, itp.), to jest prosty algorytm wielomianowy.

nie mogę dać ci biblioteki, ale w ten sposób:

For each pair of regexes r and s for languages L(r) and L(s) 
    Find the corresponding Deterministic Finite Automata M(r) and M(s) 
    Compute the cross-product machine M(r x s) and assign accepting states 
     so that it computes L(r) - L(s) 
    Use a DFS or BFS of the the M(r x s) transition table to see if any 
     accepting state can be reached from the start state 
    If no, you can eliminate s because L(s) is a subset of L(r). 
    Reassign accepting states so that M(r x s) computes L(s) - L(r) 
    Repeat the steps above to see if it's possible to eliminate r 

Konwersja regex do DFA generalnie wykorzystuje konstrukcję Thompson dostać zakaz deterministyczny automat. Zostanie to przekonwertowane na DFA przy użyciu konstrukcji podzestawu. Maszyna międzyplatformowa jest innym standardowym algorytmem.

Wszystko to zostało opracowane w latach 60. XX wieku i jest obecnie częścią każdego dobrego kursu teoretycznego z zakresu informatyki. Złotym standardem dla tego tematu jest Hopcroft and Ullman, Automata Theory.

Answer 4

Znalazłem bibliotekę regex Pythona, która udostępnia operacje zestawu.

http://github.com/ferno/greenery

Dowód mówi Sub ⊆ Sup ⇔ Sub ∩ ¬Sup is {}. mogę wdrożyć to z biblioteką Pythona:

import sys 
from greenery.lego import parse 

subregex = parse(sys.argv[1]) 
supregex = parse(sys.argv[2]) 

s = subregex&(supregex.everythingbut()) 
if s.empty(): 
    print("%s is a subset of %s"%(subregex,supregex)) 
else: 
    print("%s is not a subset of %s, it also matches %s"%(subregex,supregex,s) 

Przykłady:

subset.py abcd.* ab.* 
abcd.* is a subset of ab.* 

subset.py a[bcd]f* a[cde]f* 
a[bcd]f* is not a subset of a[cde]f*, it also matches abf* 

Biblioteka może nie być solidne, ponieważ, jak wspomniano w innych odpowiedzi trzeba użyć minimalnej DFA, aby w tym celu praca. Nie jestem pewien, czy biblioteka jest (lub może być) tą gwarancją.

Na marginesie: gra z biblioteką, aby obliczyć odwrotność lub uproszczenie wyrażeń regularnych, to dużo zabawy.
a(b|.).* upraszcza do a.+. Co jest dość minimalne.
Odwrotność abf* to ([^a]|a([^b]|bf*[^f])).*|a?. Spróbuj wymyślić to na własną rękę!