Wikipedia

Linguaggio dipendente dal contesto: differenze tra le versioni

Naviga nella cronologia in modo interattivo
← Differenza precedenteDifferenza successiva →
Contenuto cancellato Contenuto aggiunto
VisualeWikitesto
Riga 3:
=== Proprietà computationali ===
 
Computazionalmente un linguaggio sensibile al contesto è equivalente ad una lineare bounded non-deterministic [[macchina di Turing ]] non-deterministica linear bounded. ThatQuesta isè a[[macchina non-deterministicdi Turing machine]] withnon-deterministica acon tapeun ofnastro di onlysole ''kn'' cellscelle, wheredeve ''n'' isè thela size of thegrandezza dell'input ande ''k'' isè auna constantcostante associatedche withdipende thedalla machinemacchina. Questo significa che ogni linguaggio formale che può essere deciso da questa macchina è un linguaggio sensibile al contesto e che ogni linguaggio sensibile al contesto può essere deciso da una macchina del genere.
 
Questo insieme di linguaggi è conosciuto anche come '''NLIN-SPACE''', poichè possono essere accettati utilizzando uno spazio lineare su una macchina di Turing non deterministica. La classe '''LIN-SPACE''' è definita nello stesso modo, eccetto per il fatto che utilizza una macchina di Turing deterministica. Chiaramente '''LIN-SPACE''' è un sottoinsieme di un '''NLIN-SPACE''', ma non si sa se '''LIN-SPACE'''='''NLIN-SPACE'''. E' ampliamente sospettato che non siano uguali.
Estratto da "https://it.wikipedia.org/wiki/Linguaggio_dipendente_dal_contesto"