CFG står for kontekstfri grammatikk. Det er en formell grammatikk som brukes til å generere alle mulige mønstre av strenger i et gitt formelt språk. Kontekstfri grammatikk G kan defineres av fire tupler som:
G = (V, T, P, S)
Hvor,
G er grammatikken, som består av et sett av produksjonsregelen. Den brukes til å generere strengen til et språk.
T er det siste settet av et terminalsymbol. Det er merket med små bokstaver.
I er det siste settet av et ikke-terminalt symbol. Det er merket med store bokstaver.
P er et sett med produksjonsregler, som brukes til å erstatte ikke-terminalsymboler (på venstre side av produksjonen) i en streng med andre terminal- eller ikke-terminalsymboler (på høyre side av produksjonen).
indisk skuespillerinne rani mukerji
S er startsymbolet som brukes til å utlede strengen. Vi kan utlede strengen ved gjentatte ganger å erstatte en ikke-terminal med høyre side av produksjonen til alle ikke-terminale er erstattet av terminalsymboler.
Eksempel 1:
Konstruer CFG for språket som har et hvilket som helst antall a-er over settet ∑= {a}.
Løsning:
Som vi vet er det regulære uttrykket for språket ovenfor
r.e. = a*
Produksjonsregelen for det regulære uttrykket er som følger:
S → aS rule 1 S → ε rule 2
Hvis vi nå vil utlede 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
Der. = a* kan generere et sett med streng {ε, a, aa, aaa,.....}. Vi kan ha en nullstreng fordi S er et startsymbol og regel 2 gir S → ε.
Eksempel 2:
Konstruer en CFG for det regulære uttrykket (0+1)*
Løsning:
apache
CFG kan gis av,
Production rule (P): S → 0S | 1S S → ε
Reglene er i kombinasjonen av 0-er og 1-er med startsymbolet. Siden (0+1)* indikerer {ε, 0, 1, 01, 10, 00, 11, ....}. I dette settet er ε en streng, så i regelen kan vi sette regelen S → ε.
Eksempel 3:
Konstruer en CFG for et språk L = hvor w € (a, b)*.
Løsning:
Strengen som kan genereres for et gitt språk er {aacaa, bcb, abcba, bacab, abbcbba, ....}
Grammatikken kan være:
streng erstatte all java
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Hvis vi nå vil utlede 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
Dermed kan hvilken som helst av denne typen strenger avledes fra de gitte produksjonsreglene.
Eksempel 4:
Konstruer en CFG for språket L = anb2nhvor n>=1.
Løsning:
Strengen som kan genereres for et gitt språk er {abb, aabbbb, aaabbbbbb....}.
Grammatikken kan være:
S → aSbb | abb
Hvis vi nå vil utlede en streng 'aabbbb', kan vi starte med startsymboler.
S → aSbb S → aabbbb