Es sei denn, eine Grammatik ist direkt mit einer anderen Grammatik verwandt - zum Beispiel durch Standardtransformationen wie Normalisierung, Nullproduktion usw. - was beweist, dass zwei Grammatiken die gleiche Sprache ableiten, ohne dass man die Sprache kennt ist. Es ist normalerweise einfacher (unabhängig) zu beweisen, dass jede Grammatik die Sprache ableitet.
Die erste Grammatik Sie bieten:
S → aSbS | bSaS | ε
in der Tat tut leiten die Sprache aller Strings über das Alphabet {a, b}* wo die Zahl der ein s das gleiche wie die Anzahl der b s ist. Wir können das in zwei Teilen beweisen: erstens, dass jeder von der Grammatik erkannte Satz diese Eigenschaft hat, und zweitens, dass jeder Satz, der diese Eigenschaft hat, von dieser Grammatik abgeleitet werden kann. Beide Beweise laufen durch Induktion ab.
Für den Vorwärtsbeweis gehen wir durch Induktion auf die Anzahl der Ableitungen. Nehmen wir an, wir haben eine Ableitung S → α → β → … → ω, wo alle griechischen Buchstaben Sequenzen von Nicht-Terminals und Terminals darstellen.
Wenn die Länge der Ableitung genau Null ist, so dass es beginnt und endet mit S, dann gibt es keine Anschlüsse in jedem abgeleiteten Satz so ist klar, dass jeder abgeleitete Satz die gleiche Anzahl von ein s hat und b s. (Basisschritt)
Jetzt für den Induktionsschritt.Es wird angenommen, dass jede Ableitung der Länge i dafür bekannt ist, dass sie mit einem abgeleiteten Satz endet, der die gleiche Nummer a s und b s hat. Wir wollen anhand dieser Prämisse beweisen, dass jede Ableitung der Länge i+1 mit einem Satz endet, der die gleiche Nummer a s und b s hat. Aber das ist auch klar: Jeder der drei möglichen Produktionsschritte erhält Parität. Jetzt
, lassen Sie sich in der entgegengesetzten Richtung aus: jeder Satz mit der gleichen Anzahl von ein s und b s kann aus dieser Grammatik abgeleitet werden. Wir machen das durch Induktion über die Länge der Saite. Unsere Induktions Prämisse wird sein, dass, wenn es der Fall, dass für jeden j ≤ i, jeder Satz mit genau jein s und jb s eine Ableitung von S hat, dann jeden Satz mit genau i+1ein s und i+1b s. (Hier betrachten wir nur Sätze, die nur aus Anschlüssen bestehen.)
Betrachten Sie eine solche Sentence. Sie beginnt entweder mit einem a oder einem b. Angenommen, es beginnt mit einem a: dann gibt es mindestens einen b in dem Satz, so dass das Präfix, das mit dem b endet, die gleiche Nummer jedes Terminals hat. (Stellen Sie sich die Saite als einen Spaziergang entlang eines quadratischen Rasters vor: jede eine bewegt sich diagonal nach oben und nach rechts eine Einheit, und jede b bewegt sich diagonal nach unten und rechts. Da der Endpunkt genau auf der gleichen Höhe wie der Anfangspunkt und liegt Es gibt keine Wurmlöcher in der Grafik, sobald wir aufsteigen müssen wir früher oder später wieder auf die Ausgangshöhe, die ein Präfix endet b.) Also das Innere dieses Präfix (alles außer der a am Anfang und Die b am Ende) ist wie auch der Rest der Saite ausgeglichen. Beide sind kürzer, so dass sie durch die Induktions-Hypothese aus S abgeleitet werden können. Machen diese Substitutionen erhalten wir einSbS, die von S abgeleitet werden können. Ein identisches Argument gilt für Strings, die mit b beginnen. Auch hier ist der Basisschritt trivial.
Also das ist im Grunde das Beweisverfahren, das Sie für Ihre Grammatik anpassen müssen.
Viel Glück.
By the way, kann diese Art von Frage auch auf cs.stackexchange.com oder math.stackexchange.com gestellt werden, wo die Mathjax zur Verfügung steht. MathJax macht das Schreiben von mathematischen Beweisen viel weniger mühsam, so dass Sie möglicherweise feststellen werden, dass Sie dort besser lesbare Antworten erhalten.
vielleicht könnten Sie Ihre Grammatik verfeinern? Ein wenig Kontext würde helfen. –
@CalvinTaylor, Ich habe meine Frage bearbeitet!Ich füge hinzu, was ich denke, ist eine äquivalente Grammatik, aber eine Frage kam mir in den Sinn. Wie kann ich beweisen, dass sie beide gleichwertig sind? –