b"\n_START_ARTICLE_\nLinguaggio dipendente dal contesto\n_START_PARAGRAPH_\nUn linguaggio dipendente dal contesto (o anche sensibile al contesto, vincolato al contesto, o contestuale) \xc3\xa8 un linguaggio formale che pu\xc3\xb2 essere definito da una grammatica dipendente dal contesto. \xc3\x88 una dei quattro tipi di grammatica della Gerarchia di Chomsky. \xc3\x88 la meno utilizzata, sia in teoria che in pratica.\n_START_SECTION_\nPropriet\xc3\xa0 computazionali\n_START_PARAGRAPH_\nComputazionalmente un linguaggio dipendente dal contesto \xc3\xa8 equivalente ad un automa lineare limitato . Questa \xc3\xa8 una macchina di Turing non-deterministica con un nastro di sole kn celle, dove n \xc3\xa8 la grandezza dell'input e k \xc3\xa8 una costante che dipende dalla macchina. Questo significa che ogni linguaggio formale che pu\xc3\xb2 essere deciso da questa macchina \xc3\xa8 un linguaggio dipendente dal contesto e che ogni linguaggio dipendente dal contesto pu\xc3\xb2 essere deciso da una macchina del genere._NEWLINE_Questo insieme di linguaggi \xc3\xa8 conosciuto anche come NLIN-SPACE, poich\xc3\xa9 possono essere accettati utilizzando uno spazio lineare su una macchina di Turing non deterministica. La classe LIN-SPACE \xc3\xa8 definita nello stesso modo, eccetto per il fatto che utilizza una macchina di Turing deterministica. Chiaramente LIN-SPACE \xc3\xa8 un sottoinsieme di un NLIN-SPACE, ma non si sa se LIN-SPACE=NLIN-SPACE. \xc3\x88 ampiamente sospettato che non siano uguali.\n_START_SECTION_\nEsempi\n_START_PARAGRAPH_\nUn esempio di linguaggio dipendente dal contesto che non \xc3\xa8 libero dal contesto \xc3\xa8 L = { a\xe1\xb5\x96\xc2\xa0: p \xc3\xa8 un numero primo }. Il modo pi\xc3\xb9 semplice per dimostrare che si tratta di un linguaggio dipendente dal contesto \xc3\xa8 usare un automa lineare limitato. Una dimostrazione che L non \xc3\xa8 libero dal contesto pu\xc3\xb2 essere ottenuta mediante il pumping lemma."