CFG steht für kontextfreie Grammatik. Dabei handelt es sich um eine formale Grammatik, die zur Generierung aller möglichen Muster von Zeichenfolgen in einer bestimmten formalen Sprache verwendet wird. Die kontextfreie Grammatik G kann durch vier Tupel definiert werden als:
G = (V, T, P, S)
Wo,
G ist die Grammatik, die aus einer Menge der Produktionsregeln besteht. Es wird verwendet, um die Zeichenfolge einer Sprache zu generieren.
T ist der letzte Satz eines Terminalsymbols. Die Bezeichnung erfolgt durch Kleinbuchstaben.
IN ist der letzte Satz eines nichtterminalen Symbols. Es wird mit Großbuchstaben bezeichnet.
P ist eine Reihe von Produktionsregeln, die zum Ersetzen von Nicht-Terminalsymbolen (auf der linken Seite der Produktion) in einer Zeichenfolge durch andere Terminal- oder Nicht-Terminalsymbole (auf der rechten Seite der Produktion) verwendet werden.
dritte Normalform
S ist das Startsymbol, das zum Ableiten der Zeichenfolge verwendet wird. Wir können die Zeichenfolge ableiten, indem wir wiederholt ein Nicht-Terminal durch die rechte Seite der Produktion ersetzen, bis alle Nicht-Terminalsymbole durch Terminalsymbole ersetzt wurden.
Beispiel 1:
Konstruieren Sie die CFG für die Sprache mit einer beliebigen Anzahl von a über der Menge ∑= {a}.
Lösung:
Wie wir wissen, lautet der reguläre Ausdruck für die obige Sprache
r.e. = a*
Die Produktionsregel für den regulären Ausdruck lautet wie folgt:
S → aS rule 1 S → ε rule 2
Wenn wir nun eine Zeichenfolge „aaaaaa“ ableiten möchten, können wir mit Startsymbolen beginnen.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
Dort. = a* kann eine Reihe von Zeichenfolgen {ε, a, aa, aaa,......} generieren. Wir können eine Nullzeichenfolge haben, weil S ein Startsymbol ist und Regel 2 S → ε ergibt.
Beispiel 2:
Erstellen Sie eine CFG für den regulären Ausdruck (0+1)*
Lösung:
Beziehungszusammensetzung
Der CFG kann gegeben werden durch:
Production rule (P): S → 0S | 1S S → ε
Die Regeln bestehen aus der Kombination von Nullen und Einsen mit dem Startsymbol. Da (0+1)* {ε, 0, 1, 01, 10, 00, 11, ....} angibt. In dieser Menge ist ε eine Zeichenfolge, daher können wir in der Regel die Regel S → ε festlegen.
Beispiel 3:
Konstruieren Sie eine CFG für eine Sprache L = wobei w € (a, b)*.
Lösung:
Die Zeichenfolge, die für eine bestimmte Sprache generiert werden kann, ist {aacaa, bcb, abcba, bacab, abbcbba, ....}
Wie viele Städte gibt es in den Vereinigten Staaten?
Die Grammatik könnte sein:
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Wenn wir nun eine Zeichenfolge „abbcbba“ ableiten möchten, können wir mit Startsymbolen beginnen.
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
Somit kann jeder String dieser Art aus den gegebenen Produktionsregeln abgeleitet werden.
Beispiel 4:
Konstruieren Sie eine CFG für die Sprache L = aNB2nwobei n>=1.
Lösung:
Die Zeichenfolge, die für eine bestimmte Sprache generiert werden kann, ist {abb, aabbbb, aaabbbbbbb....}.
Die Grammatik könnte sein:
S → aSbb | abb
Wenn wir nun eine Zeichenfolge „aabbbb“ ableiten möchten, können wir mit Startsymbolen beginnen.
S → aSbb S → aabbbb