Inačica od 2. veljače 2020. u 13:27 uredi HmxBot (razgovor \| doprinosi) Botovi 19.624 edits m zamjena čarobnih ISBN poveznica predlošcima (mw:Requests for comment/Future of magic links) i/ili općeniti ispravci ← Starija izmjena		Posljednja izmjena od 1. siječnja 2022. u 01:15 uredi ukloni ovu izmjenu PonoRoboT (razgovor \| doprinosi) Botovi 208.673 edits m RpA: WP:NI, WP:HRV Oznaka: PAWS [2.1]
Redak 3: == 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.

Kontekstno ovisni jezik: razlika između inačica