☰

Ist es möglich, diese symmetrischen Ausdrücke über {0,1} zu egrepieren?

tag-icon • tag-icon grep
Ist es möglich, diese symmetrischen Ausdrücke über {0,1} zu egrepieren?

Das Ziel ist, ausschließlich egrep zu verwenden, um Ausdrücke abzugleichen, bei denenNAuf Vorkommen von 0 folgt genauNVorkommen von 1 und wobei auf eine 1 keine 0 folgt.

z.B

01
000111
000000111111

aber nicht:

001
011
00011

usw.

Intuitiv scheint dies nicht erreichbar zu sein, da die passenden Ausdrücke keine feste Länge haben. Aber vielleicht übersehe ich eine Funktion von egrep, die dabei nützlich sein könnte?

Antwort1

Kurzer Überblick über einige CS-Konzepte:

  • Automatenakzeptieren Zeichenfolgen, die zu einer "Sprache" gehören,durch eine „Grammatik“ erzeugt.
  • Reguläre Ausdrücke sind (theoretisch) gleichwertig mit (deterministisch oder nicht-deterministisch)endliche Automaten(DFA/NFA). Bei einem gegebenen regulären Ausdruck wie 0*1*gibt es also DFA und NFA, die Zeichenfolgen akzeptieren können, die diesem regulären Ausdruck entsprechen.
  • Endliche Automaten sind streng genommen weniger leistungsfähig alsKellerautomaten(PDA). Die von PDA akzeptierten Sprachen werden generiert durchKontextfreie Grammatiken (CFG).
  • Die Zeichenfolgen, die Sie sich ansehen, werden von der CFG generiert: (grob gesagt können Sie bei einer gegebenen Startzeichenfolge eine Zeichenfolge mit und auf beiden Seiten der Originalzeichenfolge generieren oder nichts – so können Sie , , usw. generieren).0n1nS -> 0S1 | ε01010011

Obwohl grep (erweitert oder anderweitig) über Funktionen verfügt, die über die oben genannten „regulären Ausdrücke“ hinausgehen, wie z. B. Rückverweise, glaube ich nicht, dass es dadurch so leistungsfähig wird wie ein PDA.

Man kann beweisen, dass S -> 0S1 | εnicht regulär ist, indem mandas Pump-Lemma, aber ich habe keinen Beweis dafür, dass greps Funktionen es ermöglichen, CFGs zu akzeptieren (oder nicht). Der Wikipedia-Artikel überReguläre Ausdrückehat Folgendes zu sagen (Fettdruck von mir):

Viele Funktionen, die in praktisch allen modernen Bibliotheken für reguläre Ausdrücke zu finden sind, bieten eine Ausdruckskraft, die die der regulären Sprachen bei weitem übertrifft. Viele Implementierungen ermöglichen beispielsweise das Gruppieren von Unterausdrücken mit Klammern und das Abrufen des entsprechenden Werts im selben Ausdruck (Rückverweise). Dies bedeutet unter anderem, dass ein Muster Zeichenfolgen mit wiederholten Wörtern wie „Papa“ oder „WikiWiki“ entsprechen kann, die in der formalen Sprachtheorie als Quadrate bezeichnet werden. Das Muster für diese Zeichenfolgen ist (.+)\1.

Die Sprache der Quadrate ist nicht regelmäßig,noch ist es kontextfrei, aufgrund des Pumping-Lemmas. Allerdings ist Pattern Matching mit einer unbegrenzten Anzahl von Rückverweisen, wie es von zahlreichen modernen Werkzeugen unterstützt wird, immer noch kontextsensitiv. [33]

[33]: Cezar Câmpeanu und Kai Salomaa, und Sheng Yu (Dez. 2003). „Eine formale Studie praktischer regulärer Ausdrücke“. International Journal of Foundations of Computer Science. 14 (6): 1007–1018. doi:10.1142/S012905410300214X. Theorem 3 (S.9)

Ich würde also sagen, dass man mit Sicherheit sagen kann, grepdass es nicht von selbst passt.0n1n

verwandte Informationen