Wann ist ein regulärer Ausdruck kein regulärer Ausdruck?

9

Da ich für meinen formalen Sprachkurs studiere, bin ich auf diese faszinierenden Beiträge ( One Two ) gestoßen, in denen beschrieben wird, wie man mit einem regulären Ausdruck eine Primzahl findet . Wie gesagt, ein regexp , kein regulärer Ausdruck . Da ein regulärer Ausdruck Strings entspricht durch eine Finite State Automata berechnet und eine Primzahl zu finden , kann nicht von einem FSA erfolgen, die regexp in der Blog - Post gezeigt ist nicht ganz ein regulärer Ausdruck , da es die Zeichenfolge übereinstimmt Rückzieher.

Da ich jetzt nie wirklich einen regulären Ausdruck verwendet habe, meine Frage:

Wie kann ich einen regulären Ausdruck eines "wahren" regulären Ausdrucks sofort erkennen, wenn ich ihn nur betrachte?

Definitionen: Mit regulären Ausdrücken beziehe ich mich auf den Begriff, wie er in formalen Sprachen definiert ist. Mit regulärem Ausdruck meine ich den Begriff, der von modernen Programmiersprachen unterstützt wird. Die Regexp-Syntax enthält häufig zusätzliche Funktionen, z. B. Rückreferenzen. Regexps in Programmiersprachen sind strikt leistungsfähiger als reguläre Ausdrücke im Stil formaler Sprachen.

regular-expressions Peperunas
quelle
5
Regexp ist nur eine Abkürzung für regulären Ausdruck. Die Berechnung der Primzahlen basiert auf einem Perl-Hack, nicht auf regulären Ausdrücken.
1
Es ist ziemlich einfach. Normale Sprachen verwenden Verkettung, Wiederholung und Abwechslung. Immer wenn ein Motor etwas unterstützt, das diesen nicht entspricht, ist er nicht regulär.
Kilian Foth
1
Verwandte Fragen: 1 , 2 , 3 .
Raphael
@Yannis Wenn du über den Zaun zu CS springst, stimmt das nicht mehr. Regexps, wie sie in Programmiersprachen zu sehen sind, sind strikt leistungsfähiger als reguläre Ausdrücke (im Stil formaler Sprachen), und die Kurzform "Regexp" wird konventionell (ich weiß nicht, wie weit verbreitet sie ist) für die ersteren verwendet, nicht für die letzteren nett.
Raphael
@ KilianFoth Das ist allerdings keine wirklich hilfreiche Beschreibung. Beispielsweise können Sie regulären Ausdrücken eine Negation (oder tatsächlich eine endliche Menge von Booleschen Konnektiven) hinzufügen, ohne deren Leistung zu erhöhen.
David Richerby

Antworten:

13

tl; dr backrefs.

Sobald sich im \1regulären Ausdruck eine (oder eine beliebige Zahl, die nicht zum Entkommen von Unicode verwendet wird) befindet, handelt es sich nicht um einen regulären Ausdruck.

Mit Backrefs können Sie festlegen, (a+)b\1welche Übereinstimmungen n-mal agefolgt von b gefolgt von n-mal afür n> 1 übereinstimmen . Dies ist keine reguläre Sprache (es ist das Aushängeschild einer nicht regulären Sprache).

Es ist notwendig und nahezu ausreichend, dass die Backref auf eine Gruppe verweist, die einen regulären Ausdruck enthält, der mit einer beliebig langen Zeichenfolge übereinstimmt, oder dass sie ein *oder enthält +. Die einzige Ausnahme (die ich gefunden habe) von einem regulären Ausdruck der Form, (A)B\1in der A eine endliche Sprache ist (könnte durch eine Aufzählung aller Wörter ersetzt werden, die sie akzeptieren). Sie können es in word1+Bword1|word2+Bword2usw. konvertieren, da A endlich ist.

Look-Around-Gruppen entfernen nicht die Regelmäßigkeit des regulären Ausdrucks. A(?=B)Cist der Querschnitt von regulären Ausdrücken AB.*und ACund der Querschnitt von 2 regulären Sprachen ist regelmäßig. Negativer Lookahead ist ähnlich, außer dass das Komplement von verwendet wird B.*(Komplemente regulärer Sprachen sind regulär). Lookbehind ist genau das gleiche wie A(?<=B)Cder Querschnitt von ACund .*BC.

Ratschenfreak
quelle
Ist das notwendig und ausreichend? Es sieht für mich so aus (a)\1, als ob bei Verwendung eines Backref gleichbedeutend aaund daher trivial Regular. Ich frage mich auch, ob Lookahead-Behauptungen verwendet werden können, um nicht reguläre Sprachen zu erkennen.
MSalters
1
@MSalters: Wenn Sie wirklich technisch werden möchten, (a)\1ist dies kein regulärer Ausdruck, sondern erkennt eine reguläre Sprache.
Jörg W Mittag