CFG je kratica za kontekstno-slobodnu gramatiku. To je formalna gramatika koja se koristi za generiranje svih mogućih obrazaca nizova u danom formalnom jeziku. Gramatika G bez konteksta može se definirati s četiri torke kao:
G = (V, T, P, S)
Gdje,
G je gramatika koja se sastoji od skupa pravila proizvodnje. Koristi se za generiranje niza jezika.
T je konačni skup simbola terminala. Označava se malim slovima.
U je konačni skup neterminalnog simbola. Označava se velikim slovima.
P je skup produkcijskih pravila koji se koristi za zamjenu neterminalnih simbola (na lijevoj strani produkcije) u nizu s drugim terminalnim ili neterminalnim simbolima (na desnoj strani produkcije).
string concat java
S je početni simbol koji se koristi za izvođenje niza. Niz možemo izvesti uzastopnim zamjenjivanjem ne-terminala desnom stranom produkcije sve dok se svi ne-terminali ne zamijene terminalnim simbolima.
Primjer 1:
Konstruirajte CFG za jezik koji ima bilo koji broj a u skupu ∑= {a}.
Riješenje:
Kao što znamo, regularni izraz za gornji jezik je
r.e. = a*
Pravilo proizvodnje za regularni izraz je sljedeće:
S → aS rule 1 S → ε rule 2
Sada, ako želimo izvesti niz 'aaaaaa', možemo početi s početnim simbolima.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
r.e. = a* može generirati skup nizova {ε, a, aa, aaa,.....}. Možemo imati nulti niz jer je S početni simbol i pravilo 2 daje S → ε.
Primjer 2:
Konstruirajte CFG za regularni izraz (0+1)*
Riješenje:
linux prečaci
CFG može dati,
Production rule (P): S → 0S | 1S S → ε
Pravila su u kombinaciji 0 i 1 sa simbolom starta. Budući da (0+1)* označava {ε, 0, 1, 01, 10, 00, 11, ....}. U ovom skupu ε je niz, pa u pravilu možemo postaviti pravilo S → ε.
Primjer 3:
Konstruirajte CFG za jezik L = gdje je w € (a, b)*.
Riješenje:
Niz koji se može generirati za određeni jezik je {aacaa, bcb, abcba, bacab, abbcbba, ....}
Gramatika bi mogla biti:
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Sada, ako želimo izvesti niz 'abbcbba', možemo početi s početnim simbolima.
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
Stoga se bilo koji od ove vrste niza može izvesti iz danih pravila proizvodnje.
Primjer 4:
Konstruirajte CFG za jezik L = anb2ngdje je n>=1.
Riješenje:
Niz koji se može generirati za određeni jezik je {abb, aabbbb, aaabbbbbb....}.
hadoop uputstvo
Gramatika bi mogla biti:
S → aSbb | abb
Sada, ako želimo izvesti niz 'aabbbb', možemo početi s početnim simbolima.
S → aSbb S → aabbbb