Gibt es einen Algorithmus / ein systematisches Verfahren, um zu testen, ob eine Sprache kontextfrei ist?
Mit anderen Worten, testen Sie bei einer in algebraischer Form angegebenen Sprache (denken Sie an etwas wie ), ob die Sprache kontextfrei ist oder nicht . Stellen Sie sich vor, wir schreiben einen Webdienst, der Schülern bei all ihren Hausaufgaben hilft. Sie geben die Sprache an und der Webdienst gibt "kontextfrei" oder "nicht kontextfrei" aus. Gibt es einen guten Ansatz, um dies zu automatisieren?
Natürlich gibt es Techniken für den manuellen Beweis, wie das Pump-Lemma, das Ogden-Lemma, das Parikh-Lemma, das Interchange-Lemma und vieles mehr . Sie erfordern jedoch jeweils irgendwann einen manuellen Einblick, sodass nicht klar ist, wie sie in etwas Algorithmisches umgewandelt werden können.
Ich sehe, dass Kaveh an anderer Stelle geschrieben hat, dass die Menge der nicht kontextfreien Sprachen nicht rekursiv aufzählbar ist. Es scheint also keine Hoffnung zu geben, dass ein Algorithmus für alle möglichen Sprachen funktioniert. Ich nehme daher an, dass der Webdienst in der Lage sein muss, "kontextfrei", "nicht kontextfrei" oder "Ich kann nicht sagen" auszugeben. Gibt es einen Algorithmus, der oft eine andere Antwort liefern kann als "Ich kann es nicht sagen", für viele der Sprachen, die man in Lehrbüchern findet? Wie würden Sie einen solchen Webdienst aufbauen?
Um diese Frage richtig zu stellen, müssen wir entscheiden, wie der Benutzer die Sprache spezifizieren soll. Ich bin offen für Vorschläge, aber ich denke über Folgendes nach:
Dabei ist ein Wortausdruck und ein System linearer Ungleichungen über die Längenvariablen mit den folgenden Definitionen:S
Jedes von ist ein Wortausdruck. (Dies sind Variablen, die ein beliebiges Wort in .)Σ ∗
Jeder der ist ein Wortausdruck. (Implizit ist , sodass ein einzelnes Symbol im zugrunde liegenden Alphabet darstellen.)Σ = { a , b , c , … } a , b , c , …
Jedes von ist ein Wortausdruck, wenn eine ist.η
Die Verkettung von Wortausdrücken ist ein Wortausdruck.
Jedes von ist eine Längenvariable. (Dies sind Variablen, die jede natürliche Zahl enthalten können.)
Jedes von ist eine Längenvariable. (Diese stellen die Länge eines entsprechenden Wortes dar.)
Dies scheint breit genug zu sein, um viele der Fälle zu behandeln, die wir in Schulbuchübungen sehen. Natürlich können Sie auch jede andere Textmethode zum Angeben einer Sprache in algebraischer Form verwenden, wenn Sie möchten.
Antworten:
Nach dem Satz von Rice kann nicht entschieden werden , ob die von einer Turing-Maschine akzeptierte Sprache eine nicht-triviale Eigenschaft hat (hier: kontextfrei sein). Sie müssten also die Leistung Ihrer Erkennungsmaschinerie (oder Beschreibung) einschränken, damit Turing nicht vollständig ist, um auf eine Antwort zu hoffen.
Für einige Sprachbeschreibungen ist die Antwort trivial: Wenn es sich um reguläre Ausdrücke handelt, ist es regulär, also kontextfrei. Wenn es sich um kontextfreie Grammatiken handelt, dito.
quelle
Jede Sprache, die von einem Push-Down-Automaten akzeptiert wird, ist eine CFL. Hier ist eine detaillierte Aufschlüsselung, um festzustellen, ob eine Sprache CFL ist oder nicht. Überprüfen Sie, ob die Sprache CFL ist oder nicht
quelle
Probieren Sie die JFLAP-Software aus, wenn Sie nur ein CFG überprüfen möchten. Vielleicht können Sie sogar JFLAP-Entwickler bitten, Ihnen den Code oder den Algorithmus für die Software zu geben. Sie können JFLAP hier herunterladen http://www.jflap.org/jflaptmp/ es ist kostenlos, erfordert jedoch JDK oder JRE oder so. Oder vielleicht können Sie auch andere ähnliche Software und deren Entwickler ausprobieren.
quelle