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:
dove V appartiene a N
e w è una stringa di simboli in N unione T;
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:
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.