CFG significa gramàtica lliure de context. És una gramàtica formal que s'utilitza per generar tots els patrons possibles de cadenes en un llenguatge formal determinat. La gramàtica lliure de context G es pot definir amb quatre tuples com:
G = (V, T, P, S)
On,
G és la gramàtica, que consisteix en un conjunt de la regla de producció. S'utilitza per generar la cadena d'un llenguatge.
T és el conjunt final d'un símbol terminal. Es denota amb lletres minúscules.
EN és el conjunt final d'un símbol no terminal. Es denota amb majúscules.
P és un conjunt de regles de producció, que s'utilitza per substituir símbols no terminals (a la part esquerra de la producció) en una cadena per altres símbols terminals o no terminals (a la part dreta de la producció).
substituïu la cadena a java
S és el símbol d'inici que s'utilitza per derivar la cadena. Podem derivar la cadena substituint repetidament un no terminal pel costat dret de la producció fins que tots els no terminals hagin estat substituïts per símbols terminals.
Exemple 1:
Construeix el CFG per al llenguatge que tingui qualsevol nombre de a sobre el conjunt ∑= {a}.
Solució:
Com sabem, l'expressió regular de la llengua anterior és
r.e. = a*
La regla de producció de l'expressió regular és la següent:
S → aS rule 1 S → ε rule 2
Ara, si volem derivar una cadena 'aaaaaa', podem començar amb símbols d'inici.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
El r.e. = a* pot generar un conjunt de cadenes {ε, a, aa, aaa,.....}. Podem tenir una cadena nul·la perquè S és un símbol d'inici i la regla 2 dóna S → ε.
Exemple 2:
Construeix un CFG per a l'expressió regular (0+1)*
Solució:
js conjunt
El CFG es pot donar per,
Production rule (P): S → 0S | 1S S → ε
Les regles estan en la combinació de 0 i 1 amb el símbol d'inici. Com que (0+1)* indica {ε, 0, 1, 01, 10, 00, 11, ....}. En aquest conjunt, ε és una corda, així que a la regla, podem establir la regla S → ε.
Exemple 3:
Construeix un CFG per a un llenguatge L = on w € (a, b)*.
Solució:
La cadena que es pot generar per a un idioma donat és {aacaa, bcb, abcba, bacab, abbcbba, ....}
La gramàtica podria ser:
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Ara, si volem derivar una cadena 'abbcbba', podem començar amb símbols d'inici.
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
Per tant, qualsevol d'aquest tipus de cadena es pot derivar de les regles de producció donades.
Exemple 4:
Construeix un CFG per al llenguatge L = anb2non n>=1.
abstracció en java
Solució:
La cadena que es pot generar per a un llenguatge donat és {abb, aabbbb, aaabbbbbb....}.
La gramàtica podria ser:
S → aSbb | abb
Ara, si volem derivar una cadena 'aabbbb', podem començar amb símbols d'inici.
S → aSbb S → aabbbb