A CFG a kontextusmentes nyelvtan rövidítése. Ez egy formális nyelvtan, amelyet az összes lehetséges karakterlánc-minta generálására használnak egy adott formális nyelven. A G szövegkörnyezet nélküli nyelvtan négy sorral definiálható:
G = (V, T, P, S)
Ahol,
G a nyelvtan, amely a termelési szabály halmazából áll. Egy nyelv karakterláncának generálására szolgál.
T egy terminálszimbólum utolsó halmaza. Kisbetűkkel jelöljük.
BAN BEN egy nem terminális szimbólum végső halmaza. Nagybetűkkel jelöljük.
P egy olyan gyártási szabálykészlet, amely a nem terminális szimbólumok (a produkció bal oldalán) helyettesítésére szolgál egy karakterláncban más terminális vagy nem terminális szimbólumokkal (a produkció jobb oldalán).
hogyan kell java-t nyomtatni
S a kezdőszimbólum, amely a karakterlánc származtatására szolgál. Levezethetjük a karakterláncot úgy, hogy ismételten lecserélünk egy nem terminált a produkció jobb oldalára mindaddig, amíg az összes nem terminált terminálszimbólumokkal helyettesítjük.
1. példa:
Szerkessze meg a CFG-t a ∑= {a} halmazon felül tetszőleges számú a nyelvhez.
Megoldás:
Mint tudjuk, a fenti nyelv reguláris kifejezése az
r.e. = a*
A reguláris kifejezés előállítási szabálya a következő:
S → aS rule 1 S → ε rule 2
Ha egy 'aaaaaa' karakterláncot akarunk származtatni, kezdhetjük a kezdő szimbólumokkal.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
Az r.e. = a* generálhat egy {ε, a, aa, aaa,.....} karakterlánc halmazát. Lehet null karakterláncunk, mert S egy kezdőszimbólum, és a 2. szabály S → ε értéket ad.
2. példa:
CFG létrehozása a reguláris kifejezéshez (0+1)*
Megoldás:
jfx java oktatóanyag
A CFG adható,
Production rule (P): S → 0S | 1S S → ε
A szabályok 0-k és 1-ek kombinációjában szerepelnek a start szimbólummal. Mivel a (0+1)* a következőt jelöli: {ε, 0, 1, 01, 10, 00, 11, ....}. Ebben a halmazban ε egy karakterlánc, így a szabályban beállíthatjuk az S → ε szabályt.
3. példa:
Szerkesszünk CFG-t egy L = ahol w € (a, b)* nyelvhez.
Megoldás:
Az adott nyelvhez generálható karakterlánc: {aacaa, bcb, abcba, bacab, abbcbba, ....}
A nyelvtan a következő lehet:
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Ha egy 'abbcbba' karakterláncot akarunk származtatni, kezdhetjük a start szimbólumokkal.
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
Így bármely ilyen karakterlánc származtatható az adott termelési szabályokból.
4. példa:
Szerkesszünk CFG-t az L = a nyelvheznb2nahol n>=1.
Megoldás:
Az adott nyelvhez generálható karakterlánc: {abb, aabbbb, aaabbbbbb....}.
Java metódust tartalmaz
A nyelvtan a következő lehet:
S → aSbb | abb
Ha egy 'aabbbb' karakterláncot akarunk származtatni, kezdhetjük a start szimbólumokkal.
S → aSbb S → aabbbb