grammatica dipendente dal contesto

Una grammatica dipendente dal contesto (o contestuale, context-sensitive, o anche sensibile al contesto) è una grammatica formale nella quale la forma delle produzioni ne vincola l'applicazione solo a determinati contesti. Le grammatiche dipendenti dal contesto sono più generali e potenti di quelle libere dal contesto, e sono a loro volta meno generali delle grammatiche a struttura di frase. I linguaggi descritti dalle grammatiche dipendenti dal contesto possono essere riconosciuti dagli automi lineari. Il concetto di grammatica dipendente dal contesto fu introdotto da Noam Chomsky negli anni cinquanta come modo per descrivere la sintassi di un linguaggio naturale dove si trova spesso il caso che una parola possa o non possa essere appropriata in una certa posizione a seconda del contesto. Nella gerarchia di Chomsky le grammatiche dipendenti dal contesto sono dette di Tipo 1. Un linguaggio formale che può essere descritto da una grammatica dipendente dal contesto è chiamato linguaggio dipendente dal contesto (o di Tipo 1).