Ich möchte einen regulären Ausdruck für Benutzereingaben verwenden und bestimmen, ob er mit einer Zeichenfolge übereinstimmt, d. H., Würde er auf .+ oder .* "reduziert" werden?Kann man zuverlässig feststellen, ob ein gegebener regulärer Ausdruck mit einer beliebigen Zeichenfolge übereinstimmt?
Ich vermute, dass seit this exists, dass meine Frage auf das Anhalten Problem reduzieren wird, aber ich möchte wirklich falsch darüber sein.
Ich glaube nicht, was Sie wollen, ist ähnlich dem Halting-Problem seit der Grammatik des regulären Ausdrucks. Wenn man bedenkt, dass das Alphabet und die von Ihrem Automaten erkannte Sprache endlich sind, können Sie immer noch einen Dummy-Algorithmus verwenden, der jede Welt Ihrer Sprache testen und testen würde, ob der reguläre Ausdruck sie erkennen kann oder nicht.
In der Praxis hat diese Methode eine schreckliche Komplexität, aber Sie haben keinen "undefinierten" Zustand, den Sie in Halteproblem haben würden, da die Anzahl der Eingänge aufzählbar ist.
Ich weiß eigentlich nicht, ob eine bessere Version dieses Dummy-Algorithmus existiert, aber ich hoffe, ich habe Ihre Frage zur Ähnlichkeit mit dem Halting-Problem beantwortet.
Der Grund, warum ich dachte, es könnte zu einem Problem werden, war, dass ich gedacht hatte, dass es keinen besseren Weg geben würde, einen regulären Ausdruck zu analysieren, als Techniken wie die in dem Modul zu verwenden, das ich verlinkt habe. Wenn das der Fall gewesen wäre, würde die Frage lauten: "Ist diese Liste einzigartiger Strings unendlich?" Testen gegen bekannte Wörter ist nicht ausreichend. –
Kleene Star oder '*' ist technisch in einem theoretischen Aspekt unendlich, aber dieses Modul hat Tests für bis zu 32767 Wiederholungen mit '*' gepostet. – squiguy
Wie überprüft man, ob die Eingabe nicht leer/leer/null/null ist? Da Sie keine anderen Kriterien haben, solange die Benutzereingabe _something_ es Ihren Anforderungen entspricht. –
@Burhan Khalid Sie missverstehen die Frage. Er möchte testen, ob eine beliebige Regex zu einer Zeichenfolge passt oder nicht. – Patashu