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 = aⁿb²ⁿhvor 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