CFG reiškia bekontekstinę gramatiką. Tai yra formali gramatika, kuri naudojama generuoti visus galimus eilučių modelius tam tikra oficialia kalba. Gramatika be konteksto G gali būti apibrėžta keturiomis eilėmis kaip:
G = (V, T, P, S)
kur,
G yra gramatika, kurią sudaro gamybos taisyklės rinkinys. Jis naudojamas kalbos eilutei generuoti.
T yra galutinis terminalo simbolio rinkinys. Jis žymimas mažosiomis raidėmis.
IN yra galutinis negalinio simbolio rinkinys. Jis žymimas didžiosiomis raidėmis.
P yra gamybos taisyklių rinkinys, kuris naudojamas ne terminalų simboliams (kairėje produkcijos pusėje) pakeisti eilutėje kitais terminalo arba negaliniais simboliais (dešinėje produkcijos pusėje).
teksto įvynioklis css
S yra pradžios simbolis, naudojamas eilutei išvesti. Mes galime išvesti eilutę pakartotinai pakeisdami ne terminalą dešiniąja produkcijos puse, kol visi ne terminalai bus pakeisti terminalo simboliais.
1 pavyzdys:
Sukurkite CFG kalbai, turinčiai bet kokį a skaičių virš aibės ∑= {a}.
Sprendimas:
Kaip žinome, pirmiau nurodytos kalbos reguliarioji išraiška yra
r.e. = a*
Reguliariosios išraiškos gamybos taisyklė yra tokia:
S → aS rule 1 S → ε rule 2
Dabar, jei norime išvesti eilutę „aaaaaa“, galime pradėti nuo pradžios simbolių.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
R.e. = a* gali generuoti eilutės aibę {ε, a, aa, aaa,.....}. Galime turėti nulinę eilutę, nes S yra pradžios simbolis, o 2 taisyklė suteikia S → ε.
2 pavyzdys:
Sukurkite reguliariosios išraiškos CFG (0+1)*
Sprendimas:
kibirkšties pamoka
CFG gali būti suteiktas
Production rule (P): S → 0S | 1S S → ε
Taisyklės yra 0 ir 1 derinys su pradžios simboliu. Kadangi (0+1)* reiškia {ε, 0, 1, 01, 10, 00, 11, ....}. Šioje aibėje ε yra eilutė, todėl taisyklėje galime nustatyti taisyklę S → ε.
3 pavyzdys:
Sukurkite CFG kalbai L = kur w € (a, b)*.
Sprendimas:
Eilutė, kurią galima sugeneruoti nurodytai kalbai, yra {aacaa, bcb, abcba, bacab, abbcbba, ....}
Gramatika gali būti tokia:
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Dabar, jei norime išvesti eilutę „abbcbba“, galime pradėti nuo pradžios simbolių.
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
Taigi bet kuri šios rūšies eilutė gali būti išvesta iš pateiktų gamybos taisyklių.
4 pavyzdys:
Sukurkite CFG kalbai L = anb2nkur n>=1.
Sprendimas:
Eilutė, kurią galima sugeneruoti nurodytai kalbai, yra {abb, aabbbb, aaabbbbbb....}.
java int eilutėje
Gramatika gali būti tokia:
S → aSbb | abb
Dabar, jei norime išvesti eilutę „aabbbb“, galime pradėti nuo pradžios simbolių.
S → aSbb S → aabbbb