Kontekstno ovisni jezik: razlika između inačica

m
RpA: WP:NI, WP:HRV
m (zamjena čarobnih ISBN poveznica predlošcima (mw:Requests for comment/Future of magic links) i/ili općeniti ispravci)
m (RpA: WP:NI, WP:HRV)
 
== Računska svojstva ==
 
Računski su kontekstno ovisni jezici istovjetni linearno ograničenom nedeterminističkom [[Turingov stroj|Turingovom stroju]]. To jest, nedeterminističkom Turingovom stroju sas trakom od samo ''kn'' ćelija, gdje je ''n'' veličina ulaza i ''k'' konstanta asocirana sa strojem. Ovo znači da svaki formalni jezik kojeg takav stroj odlučuje jest kontekstno ovisni jezik, i svaki kontekstno ovisni jezik može biti odlučen takvim strojem.
 
Ovaj skup jezika je također poznat kao '''NLIN-SPACE''' pošto mogu biti prihvaćeni korištenjem linearnog prostora na nedeterminističkom Turingovom stroju. Klasa složenosti '''LIN-SPACE''' je definirana na sličan način, osim što koristi deterministički Turingov stroj. Očito slijedi da je '''LIN-SPACE''' podskup od '''NLIN-SPACE''', ali se ne zna vrijedi li '''LIN-SPACE'''='''NLIN-SPACE'''. Pretpostavlja se da te dvije klase nisu jednake.
150.596

uređivanja