Grammatiche context-free

---

Le grammatiche context-free sono una delle tipologie di grammatiche presenti nella gerarchia delle grammatiche proposta da N. Chomsky.

Una grammatica context-free si definisce come l'insieme di:

• Un insieme finito N di simboli non terminali;
• Un insieme finito T, disgiunto da N, di simboli terminali;
• Un insieme finito P di regole di produzione, nella forma

V → w

dove V appartiene a N e w è una stringa di simboli in N unione T;

• Un simbolo iniziale S appartenente a N.

Il linguaggio generato da questa grammatica è dato da tutte le stringhe di soli simboli terminali ottenute da S applicando le regole di produzione.

Ad esempio, la grammatica che genera tutte le stringhe di a e b che iniziano con a e finiscono con b è data da:

• Simboli non terminali: S, T.
• Simboli terminali: a, b
• Regole di produzione: (S → aT, T → aT, T → bT, T → b)
• Simbolo iniziale: S

Esistono linguaggi (anche linguaggi decidibili!) che non sono generabili da grammatiche libere dal contesto: pertanto, in certi casi può essere necessario ricorrere a strumenti più potenti.

Comunque, solitamente le grammatiche libere dal contesto sono strumenti più che sufficienti per la produzione dell'insieme delle formule ben formate.