Ausdruckskraft moderner regulärer Ausdrücke

9

Ich habe kürzlich mit einem Freund über eine Website gesprochen, auf der Regex-Herausforderungen vorgeschlagen wurden, wobei hauptsächlich eine Gruppe von Wörtern mit einer speziellen Eigenschaft abgeglichen wurde. Er suchte nach einem regulären Ausdruck, der zu Zeichenfolgen passt, bei ||||||||denen die Anzahl der |Primzahlen ist. Ich sagte ihm sofort, dass dies niemals funktionieren wird, denn wenn eine solche Sprache regelmäßig wäre, würde die Übersetzung des Pump-Lemmas die Tatsache ergeben, dass für eine Primzahl groß genug ist, so dass Primzahl für alle ist , und nun, dies ist wahrscheinlich überhaupt nicht der Fall (Aufteilung der Primzahlen, Trivialität einer solchen unbekannten und zerstörerischen Eigenschaft, ...)pkpp+nkn- -1

Aber dann kam jemand mit der Lösung: NOT MATCHING (||+?)\1+ Dieser Ausdruck versucht , die Capture - Gruppe übereinstimmen (das kann sein ||, |||, ||||und so weiter von Vorkommen ) mal. Wenn es übereinstimmt, bedeutet dies, dass die durch die Zeichenfolge dargestellte Zahl durch teilbar ist und daher keine Primzahl ist. Ansonsten ist es.k2|n2k

Und ich fühlte mich dumm, weil es offensichtlich wurde, dass durch Gruppierung und Rückreferenz Regex tatsächlich viel ausdrucksvoller ist als ... regulärer Ausdruck im theoretischen Sinne. Jetzt haben sie sogar Lookarounds und andere Operatoren hinzugefügt, von denen ich nicht wusste, wann ich echte Regex gemacht habe.

Noch ausdrucksvoller ist es, dass Sprachen durch eine kontextfreie Grammatik erzeugt werden. Also hier ist meine Frage:

  • Können wir jede algebraische Sprache (generiert aus einer kontextfreien Grammatik) mit modernen Engines-Engines darstellen?
  • Gibt es eine allgemeinere Beschreibung oder zumindest eine Obergrenze für die Komplexität welcher Sprachen, die von einem modernen regulären Ausdruck beschrieben werden können?

Was pragmatischer ist, gibt es eine ernsthafte Theorie dahinter oder fügen wir nur neue Funktionen hinzu, wenn sie jedes Mal in den anfänglichen Block realer regulärer Ausdrücke implementiert werden, die auf endlichen Automaten basieren?

Ich weiß, dass "moderne Regex" nicht sehr spezifisch ist, während die Frage ist, aber ich meine zumindest mit Rückreferenzen und möglicherweise mehr. Wenn Sie teilweise Antworten haben, die bestimmte Einschränkungen für diese "moderne Regex" -Sprache annehmen, können Sie diese gerne posten.

yago
quelle
1
Verwandte Frage . Ich scheine mich zu erinnern, dass zumindest einige RegExp-Aromen vollständig sind. Dieser Artikel kann ein gültiger Ausgangspunkt für die Literaturrecherche sein.
Raphael
@ Raphael vielen Dank, der Artikel scheint auf einen großen Teil meiner Verhöre zu antworten
yago
Ein stärkerer Grund, warum nicht alle p + nk Primzahlen sein können, ist, dass wenn n = p ist, Sie p + nk = p (1 + k) haben.
Nathan FD

Antworten: