Rahmen:
- reguläre Ausdrücke mit Rückverweisen
- unäre Sprache (1-Symbol-Alphabet)
Kann das folgende Problem in dieser Einstellung behoben werden:
- Definiert ein regulärer Ausdruck mit Rückverweisen eine reguläre Sprache?
Definiert beispielsweise (aa+)\1eine reguläre Sprache, während (aa+)\1+dies nicht der Fall ist. Können wir uns entscheiden, was der Fall ist?
Der Vollständigkeit halber beziehen sich "reguläre Ausdrücke mit Rückverweisen" hier z. B. auf die folgende Teilmenge der üblichen Perl-kompatiblen regulären Ausdrücke :
aStimmt mit dem Zeichen übereina(das einzige Zeichen im Alphabet)X*Stimmt mit 0 oder mehr Vorkommen von übereinXX|YStreichhölzerXoderY- Klammern können zum Gruppieren und Erfassen verwendet werden
\1.\2usw. stimmen mit derselben Zeichenfolge überein wie mit dem ersten, zweiten usw. Klammerpaar
Wir können auch die normalen Abkürzungen verwenden, zB X+= XX*.
formal-languages
computability
regular-languages
undecidability
regular-expressions
Jukka Suomela
quelle
quelle
Antworten:
Ein Beweis für die effektive Entscheidbarkeit des Problems ist die Konstruktion im Beweis von Satz 9 in meinem Aufsatz Über praktische reguläre Ausdrücke : Sie könnten feststellen, ob es endlich viele Fermat-Primzahlen gibt.
quelle