CFG står för kontextfri grammatik. Det är en formell grammatik som används för att generera alla möjliga mönster av strängar i ett givet formellt språk. Kontextfri grammatik G kan definieras av fyra tuplar som:
G = (V, T, P, S)
Var,
G är grammatiken, som består av en uppsättning av produktionsregeln. Den används för att generera strängen för ett språk.
T är den sista uppsättningen av en terminalsymbol. Det betecknas med små bokstäver.
I är den sista uppsättningen av en icke-terminal symbol. Det betecknas med versaler.
P är en uppsättning produktionsregler, som används för att ersätta icke-terminalsymboler (på vänster sida av produktionen) i en sträng med andra terminal- eller icke-terminalsymboler (på höger sida av produktionen).
handledning för javafx
S är startsymbolen som används för att härleda strängen. Vi kan härleda strängen genom att upprepade gånger ersätta en icke-terminal med den högra sidan av produktionen tills alla icke-terminala har ersatts av terminalsymboler.
Exempel 1:
Konstruera CFG för språket som har ett valfritt antal a över uppsättningen ∑= {a}.
Lösning:
Som vi vet är det reguljära uttrycket för ovanstående språk
r.e. = a*
Produktionsregeln för det reguljära uttrycket är följande:
S → aS rule 1 S → ε rule 2
Om vi nu vill härleda en sträng 'aaaaaa', kan vi börja med startsymboler.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
Där. = a* kan generera en uppsättning sträng {ε, a, aa, aaa,.....}. Vi kan ha en nollsträng eftersom S är en startsymbol och regel 2 ger S → ε.
Exempel 2:
Konstruera en CFG för det reguljära uttrycket (0+1)*
Lösning:
java check är null
CFG kan ges av,
Production rule (P): S → 0S | 1S S → ε
Reglerna är i kombinationen av 0:or och 1:or med startsymbolen. Eftersom (0+1)* indikerar {ε, 0, 1, 01, 10, 00, 11, ....}. I denna mängd är ε en sträng, så i regeln kan vi sätta regeln S → ε.
Exempel 3:
Konstruera en CFG för ett språk L = där w € (a, b)*.
Lösning:
Strängen som kan genereras för ett givet språk är {aacaa, bcb, abcba, bacab, abbcbba, ....}
Grammatiken kan vara:
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Om vi nu vill härleda en sträng 'abbcbba' kan vi börja med startsymboler.
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
Således kan vilken som helst av denna typ av sträng härledas från de givna produktionsreglerna.
Exempel 4:
Konstruera en CFG för språket L = anb2ndär n>=1.
Lösning:
Strängen som kan genereras för ett givet språk är {abb, aabbbb, aaabbbbbb....}.
Grammatiken kan vara:
relationssammansättning
S → aSbb | abb
Om vi nu vill härleda en sträng 'aabbbb' kan vi börja med startsymboler.
S → aSbb S → aabbbb