CFG apzīmē bezkonteksta gramatiku. Tā ir formāla gramatika, ko izmanto, lai ģenerētu visus iespējamos virkņu modeļus noteiktā formālā valodā. Bezkonteksta gramatiku G var definēt ar četriem kortežiem kā:
G = (V, T, P, S)
kur,
G ir gramatika, kas sastāv no ražošanas noteikumu kopas. To izmanto, lai ģenerētu valodas virkni.
T ir termināļa simbola galīgā kopa. To apzīmē ar mazajiem burtiem.
IN ir netermināla simbola galīgā kopa. To apzīmē ar lielajiem burtiem.
P ir ražošanas noteikumu kopums, ko izmanto, lai virknē aizstātu simbolus, kas nav termināļi (produkcijas kreisajā pusē), ar citiem termināla vai bezgala simboliem (produkcijas labajā pusē).
json json piemērā
S ir sākuma simbols, ko izmanto virknes atvasināšanai. Mēs varam atvasināt virkni, atkārtoti aizstājot neterminālu ar produkcijas labo pusi, līdz visi termināli, kas nav termināli, ir aizstāti ar termināļa simboliem.
1. piemērs:
Izveidojiet CFG valodai, kurai ir jebkurš a skaits virs kopas ∑= {a}.
Risinājums:
Kā mēs zinām, iepriekš minētās valodas regulārā izteiksme ir
r.e. = a*
Regulārās izteiksmes ražošanas noteikums ir šāds:
S → aS rule 1 S → ε rule 2
Tagad, ja mēs vēlamies iegūt virkni 'aaaaaa', mēs varam sākt ar sākuma simboliem.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
R.e. = a* var ģenerēt virknes kopu {ε, a, aa, aaa,.....}. Mums var būt nulles virkne, jo S ir sākuma simbols un 2. noteikums dod S → ε.
2. piemērs:
Izveidojiet CFG regulārai izteiksmei (0+1)*
Risinājums:
c++ komplekts
CFG var piešķirt,
Production rule (P): S → 0S | 1S S → ε
Noteikumi ir 0 un 1 kombinācijā ar starta simbolu. Tā kā (0+1)* norāda {ε, 0, 1, 01, 10, 00, 11, ....}. Šajā kopā ε ir virkne, tāpēc noteikumā mēs varam iestatīt noteikumu S → ε.
3. piemērs:
Izveidojiet CFG valodai L = kur w € (a, b)*.
Risinājums:
Virkne, ko var ģenerēt noteiktai valodai, ir {aacaa, bcb, abcba, bacab, abbcbba, ....}
Gramatika varētu būt:
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Tagad, ja mēs vēlamies iegūt virkni 'abbcbba', mēs varam sākt ar sākuma simboliem.
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
Tādējādi jebkuru šāda veida virkni var iegūt no dotajiem ražošanas noteikumiem.
java salīdzināms
4. piemērs:
Izveidojiet CFG valodai L = anb2nkur n>=1.
Risinājums:
Virkne, ko var ģenerēt noteiktai valodai, ir {abb, aabbbb, aaabbbbbb....}.
Gramatika varētu būt:
S → aSbb | abb
Tagad, ja mēs vēlamies iegūt virkni 'aabbbb', mēs varam sākt ar sākuma simboliem.
S → aSbb S → aabbbb