CFG je kratica za slovnico brez konteksta. To je formalna slovnica, ki se uporablja za ustvarjanje vseh možnih vzorcev nizov v danem formalnem jeziku. Slovnico brez konteksta G lahko definiramo s štirimi tuplemi kot:
G = (V, T, P, S)
Kje,
G je slovnica, ki je sestavljena iz niza produkcijskih pravil. Uporablja se za ustvarjanje niza jezika.
T je končni niz simbola terminala. Označena je z malimi črkami.
IN je končni niz neterminalnega simbola. Označujemo ga z velikimi črkami.
p je niz produkcijskih pravil, ki se uporablja za zamenjavo neterminalnih simbolov (na levi strani produkcije) v nizu z drugimi terminalskimi ali neterminalnimi simboli (na desni strani produkcije).
algoritem za binarno iskanje
S je začetni simbol, ki se uporablja za izpeljavo niza. Niz lahko izpeljemo tako, da večkrat zamenjamo ne-terminal z desno stranjo proizvodnje, dokler vsi ne-terminali niso zamenjani s terminalskimi simboli.
Primer 1:
Konstruirajte CFG za jezik, ki ima poljubno število a-jev nad množico ∑= {a}.
rešitev:
Kot vemo, je regularni izraz za zgornji jezik
r.e. = a*
Produkcijsko pravilo za regularni izraz je naslednje:
S → aS rule 1 S → ε rule 2
Zdaj, če želimo izpeljati niz 'aaaaaa', lahko začnemo z začetnimi 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* lahko ustvari nabor nizov {ε, a, aa, aaa,.....}. Lahko imamo ničelni niz, ker je S začetni simbol in pravilo 2 daje S → ε.
Primer 2:
Izdelajte CFG za regularni izraz (0+1)*
rešitev:
koliko filmov misija nemogoče je
CFG lahko poda,
Production rule (P): S → 0S | 1S S → ε
Pravila so v kombinaciji 0 in 1 s simbolom za začetek. Ker (0+1)* označuje {ε, 0, 1, 01, 10, 00, 11, ....}. V tem nizu je ε niz, zato lahko v pravilu nastavimo pravilo S → ε.
Primer 3:
Konstruirajte CFG za jezik L = kjer je w € (a, b)*.
rešitev:
Niz, ki ga je mogoče ustvariti za dani jezik, je {aacaa, bcb, abcba, bacab, abbcbba, ....}
Slovnica je lahko:
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Zdaj, če želimo izpeljati niz 'abbcbba', lahko začnemo z začetnimi simboli.
vzorec javascripta
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
Tako lahko kateri koli niz te vrste izpeljemo iz danih proizvodnih pravil.
Primer 4:
Konstruirajte CFG za jezik L = anb2nkjer je n>=1.
rešitev:
Niz, ki ga je mogoče ustvariti za določen jezik, je {abb, aabbbb, aaabbbbbb....}.
Slovnica je lahko:
S → aSbb | abb
Zdaj, če želimo izpeljati niz 'aabbbb', lahko začnemo z začetnimi simboli.
S → aSbb S → aabbbb