Grammatiche generative
Sistema di riscrittura utilizzato per definire linguaggi formali mediante la loro generazione.Formalmente una grammatica G è una quadrupla (X,V,S,P) composta da:
- X: alfabeto dei simboli terminali
- V: alfabeto delle variabili o simboli non terminali
- S: simbolo distintivo o scopo della grammatica (appartiene a V)
- P: insieme di coppie (v,w) di stringhe dette produzioni costruite sull'unione dei due alfabeti, denotate anche con v --> w
Il linguaggio generato dalla grammatica è costituito da tutte le stringhe di terminali che possono essere ottenute partendo dal simbolo S ed applicando una produzione alla volta alle forme di frase via via prodotte.
