Linguaggio context-sensitive

linguaggio context-sensitive

linguaggio context-sensitive linguaggio formale generato da una → grammatica generativa G = 〈A_N, A, P, s〉, dove A è l’alfabeto dei simboli terminali, A_N è l’alfabeto dei simboli non terminali, s ∈ A_N è l’assioma, P è un insieme di regole di riscrittura (produzioni) del tipo α → β, così intendendo che la stringa a sinistra della freccia può essere rimpiazzata da quella a destra, con |α| ≤ |β|, α, β ∈ (A_N ∪ A)*. Tali regole indicano che sia a sinistra sia a destra compare una stringa di simboli, terminali e non terminali; che tali stringhe possono anche essere vuote, ma che comunque quella a sinistra ha lunghezza minore o uguale di quella di destra (le due barrette indicano la lunghezza della stringa che racchiudono). Queste produzioni sono di tipo generale e, poiché a sinistra c’è una stringa e non un singolo simbolo, la sostituzione di uno o più simboli avviene soltanto nel contesto in cui esso o essi si trovano: da qui l’indicazione che il linguaggio generato da una grammatica di questo tipo è sensibile al contesto (context-sensitive). Linguaggi di questo tipo hanno una difficile trattabilità automatica, proprio per la loro dipendenza dal contesto, e sono poco utilizzabili come linguaggi di programmazione. Il loro impiego, sulla base di studi condotti soprattutto dal linguista Noam Chomsky (1928), è stato proposto nell’ambito della formalizzazione dei linguaggi naturali e in relazione ai problemi, ancora non del tutto risolti in modo soddisfacente, di traduzione automatica da una lingua naturale a un’altra.