Ich bin neu bei CFG's,
Kann mir jemand Tipps zum Erstellen von CFG geben, das eine Sprache generiert?
Zum Beispiel
L = {am bn | m >= n}
Was ich habe ist:
So -> a | aSo | aS1 | e
S1 -> b | bS1 | e
Aber ich denke, dieser Bereich ist falsch, weil die Wahrscheinlichkeit besteht, dass die Anzahl der b größer als a ist.
L = {a m b n | m & gt; = n}.
Sprachbeschreibung: a m b n besteht aus a gefolgt von b wobei die Anzahl der a gleich oder größer als die Anzahl der b ist.
einige Beispielstrings: {^, a, aa, aab, aabb, aaaab, ab......}
Es gibt also immer ein a für ein b , aber extra a sind möglich. infize string kann nur aus a bestehen. Beachten Sie auch, dass ^ null ein Mitglied der Sprache ist, weil in ^ NumberOf(a) = NumberOf(b) = 0
Wie schreibe ich eine Grammatik, die die Sprache akzeptiert, die von Strings a m b n gebildet wird?
In der Grammatik sollte es Regeln geben, dass Sie, wenn Sie ein b -Symbol hinzufügen, auch ein a -Symbol hinzufügen.
und das kann mit etwas wie:
gemacht werden %Vor% Aber das ist unvollständig, weil wir eine Regel brauchen, um extra a s zu generieren:
Kombinieren Sie zwei Produktionsregeln zu einer einzigen Grammatik CFG.
%Vor% Sie können also jede Zeichenfolge generieren, die aus a und a und b in (a besteht m b n ) Muster.
In der obigen Grammatik gibt es jedoch no , um ^ string zu generieren.
Also ändere diese Grammatik wie folgt:
%Vor%Diese Grammatik kann {a m b n | erzeugen m & gt; = n} Sprache.
Hinweis : Um ^ null string zu generieren, habe ich einen zusätzlichen ersten Grammatikschritt hinzugefügt, indem ich S--> B | ^ hinzufüge. Sie können also entweder ^ oder die Zeichenfolge des Symbols hinzufügen a und b . ( jetzt B spielt die Rolle von S aus der vorherigen Grammatik, um die gleiche Anzahl von a und b zu generieren)
Bearbeiten: Danke an @Andy Hayden
Sie können auch äquivalente Grammatik für dieselbe Sprache schreiben {a m b n | m & gt; = n}:
Hinweis: Hier kann A --> aA | ^ null oder eine beliebige Anzahl von a generieren. Und das sollte meiner Grammatik vorzuziehen sein, weil es einen kleineren Syntaxbaum für die gleiche Zeichenkette erzeugt
( in der Höhe vorzuziehen wegen der effizienten Analyse )
Die folgenden Tipps können hilfreich sein, Grammatik für eine formale Sprache zu schreiben:
- Sie müssen sich über Sprache im Klaren sein, was sie beschreibt (Bedeutung / Muster).
- Sie können sich Lösungen für einige grundlegende Probleme merken (die Idee ist, dass Sie neue Grammatiken schreiben können).
- Sie können Regeln für grundlegende Sprachen schreiben wie Ich habe für RE geschrieben In diesem Beispiel schreiben Sie rechts-linear-Grammmar . Die Regeln werden Ihnen helfen, Grammatik für neue Sprachen zu schreiben.
- Ein anderer Ansatz besteht darin, zuerst Automaten zu zeichnen und anschließend Automaten in Grammatik umzuwandeln. Wir haben vordefinierte Techniken zum Schreiben von Grammatik aus Automaten aus jeder Klasse von Formensprache.
- Wie ein guter Programmierer, der lernt, indem er den Code anderer liest, kann man ähnlich lernen, Grammatiken für formale Sprachen zu schreiben.
Auch die Grammatik, die Sie geschrieben haben, ist falsch.
Sie möchten eine Grammatik für die folgende Sprache erstellen
%Vor%Das bedeutet, dass die Anzahl von 'b' größer oder gleich der Anzahl von 'a' sein sollte oder man kann sagen, dass für jedes "b" höchstens ein "a" existieren könnte. nicht anders herum.
Hier ist Grammatik für diese Sprache
%Vor%In dieser Grammatik gibt es für jedes "a" ein "b". aber b kann erzeugt werden, ohne irgendein 'a' zu erzeugen.
Sie können diese Sprachen auch ausprobieren:
%Vor%Ich gebe Grammatik für jede Sprache.
für L1
%Vor%für L2
%Vor%für L3
%Vor%für L4
%Vor%Tags und Links lexical-analysis grammar context-free-grammar formal-languages