CFG staat voor contextvrije grammatica. Het is een formele grammatica die wordt gebruikt om alle mogelijke tekenreekspatronen in een bepaalde formele taal te genereren. Contextvrije grammatica G kan worden gedefinieerd door vier tupels als:
G = (V, T, P, S)
Waar,
G is de grammatica, die bestaat uit een reeks productieregels. Het wordt gebruikt om de string van een taal te genereren.
T is de laatste set van een terminalsymbool. Het wordt aangegeven met kleine letters.
IN is de laatste set van een niet-terminal symbool. Het wordt aangegeven met hoofdletters.
P is een set productieregels, die wordt gebruikt voor het vervangen van niet-terminale symbolen (aan de linkerkant van de productie) in een string door andere terminale of niet-terminale symbolen (aan de rechterkant van de productie).
c programmareeksarray
S is het startsymbool dat wordt gebruikt om de string af te leiden. We kunnen de string afleiden door herhaaldelijk een niet-terminal te vervangen door de rechterkant van de productie totdat alle niet-terminale symbolen zijn vervangen door terminale symbolen.
Voorbeeld 1:
Construeer de CFG voor de taal met een willekeurig aantal a's over de verzameling ∑= {a}.
Oplossing:
Zoals we weten is de reguliere expressie voor de bovenstaande taal
r.e. = a*
De productieregel voor de reguliere expressie is als volgt:
S → aS rule 1 S → ε rule 2
Als we nu een string 'aaaaaa' willen afleiden, kunnen we beginnen met startsymbolen.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
Daar. = a* kan een reeks strings {ε, a, aa, aaa,.....} genereren. We kunnen een nulreeks hebben omdat S een startsymbool is en regel 2 S → ε geeft.
Voorbeeld 2:
Construeer een CFG voor de reguliere expressie (0+1)*
Oplossing:
converteer tekenreeks naar char java
De CFG kan worden gegeven door,
Production rule (P): S → 0S | 1S S → ε
De regels zijn in de combinatie van 0-en en 1-en met het startsymbool. Omdat (0+1)* {ε, 0, 1, 01, 10, 00, 11, ....} aangeeft. In deze set is ε een string, dus in de regel kunnen we de regel S → ε instellen.
Voorbeeld 3:
Construeer een CFG voor een taal L = waarbij w € (a, b)*.
Oplossing:
De string die voor een bepaalde taal kan worden gegenereerd is {aacaa, bcb, abcba, bacab, abbcbba, ....}
De grammatica zou kunnen zijn:
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Als we nu een string 'abbcbba' willen afleiden, kunnen we beginnen met startsymbolen.
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
Elk van dit soort strings kan dus worden afgeleid van de gegeven productieregels.
Java-thread maken
Voorbeeld 4:
Construeer een CFG voor de taal L = aNB2nwaarbij n>=1.
Oplossing:
De string die voor een bepaalde taal kan worden gegenereerd is {abb, aabbbb, aaabbbbbb....}.
De grammatica zou kunnen zijn:
S → aSbb | abb
Als we nu een string 'aabbbb' willen afleiden, kunnen we beginnen met startsymbolen.
S → aSbb S → aabbbb