CFG står for kontekstfri grammatik. Det er en formel grammatik, som bruges til at generere alle mulige mønstre af strenge i et givet formelt sprog. Kontekstfri grammatik G kan defineres af fire tuples som:
G = (V, T, P, S)
Hvor,
G er grammatikken, som består af et sæt af produktionsreglen. Det bruges til at generere strengen i et sprog.
T er det sidste sæt af et terminalsymbol. Det er angivet med små bogstaver.
I er det sidste sæt af et ikke-terminalt symbol. Det er angivet med store bogstaver.
P er et sæt produktionsregler, som bruges til at erstatte ikke-terminalsymboler (på venstre side af produktionen) i en streng med andre terminal- eller ikke-terminalsymboler (på højre side af produktionen).
1 million hvor mange 0
S er startsymbolet, som bruges til at udlede strengen. Vi kan udlede strengen ved gentagne gange at erstatte en ikke-terminal med den højre side af produktionen, indtil alle ikke-terminaler er blevet erstattet af terminalsymboler.
Eksempel 1:
Konstruer CFG'en for sproget med et vilkårligt antal a'er over sættet ∑= {a}.
Løsning:
Som vi ved er det regulære udtryk for ovenstående sprog
r.e. = a*
Produktionsreglen for det regulære udtryk er som følger:
S → aS rule 1 S → ε rule 2
Hvis vi nu vil udlede en streng 'aaaaaa', kan vi starte med startsymboler.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
Den r.e. = a* kan generere et sæt streng {ε, a, aa, aaa,.....}. Vi kan have en nulstreng, fordi S er et startsymbol og regel 2 giver S → ε.
Eksempel 2:
Konstruer en CFG for det regulære udtryk (0+1)*
Løsning:
centos vs rhel
CFG kan gives af,
Production rule (P): S → 0S | 1S S → ε
Reglerne er i kombinationen af 0'er og 1'er med startsymbolet. Da (0+1)* angiver {ε, 0, 1, 01, 10, 00, 11, ....}. I dette sæt er ε en streng, så i reglen kan vi sætte reglen S → ε.
Eksempel 3:
Konstruer en CFG for et sprog L = hvor w € (a, b)*.
Løsning:
Den streng, der kan genereres for et givet sprog er {aacaa, bcb, abcba, bacab, abbcbba, ....}
Grammatikken kunne være:
strsep c
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Hvis vi nu vil udlede en streng 'abbcbba', kan vi starte med startsymboler.
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
En hvilken som helst af denne slags strenge kan således udledes fra de givne produktionsregler.
Eksempel 4:
Konstruer en CFG for sproget L = anb2nhvor n>=1.
Løsning:
Den streng, der kan genereres for et givet sprog, er {abb, aabbbb, aaabbbbbb....}.
Grammatikken kunne være:
S → aSbb | abb
Hvis vi nu vil udlede en streng 'aabbbb', kan vi starte med startsymboler.
S → aSbb S → aabbbb