Kontekstno ovisni jezik: razlika između inačica

+ref
m (robot Dodaje: bs:Kontekstno zavisni jezik)
(+ref)
'''Kontekstno ovisni jezik''' je [[formalni jezik]] koji se može definirati [[kontekstno ovisna gramatika|kontekstno ovisnom gramatikom]], koja je jedan od četiri tipa gramatika u [[Chomskyjeva hijerarhija|Chomskyjevoj hijerarhiji]]. Najmanje je korištena od sve četiri, kako u teoriji tako i u praksi.
 
== KomputacijskaRačunska svojstva ==
 
KomputacijskiRačunski su kontekstno ovisni jezici istovjetni linearno ograničenom nedeterminističkom [[Turingov stroj|Turingovom stroju]]. To jest, nedeterminističkom Turingovom stroju sa 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.
* Komplement kontekstno ovisnog jezika jest i sam kontekstno ovisan.
* Svaki [[kontekstno neovisni jezik|kontekstno neovisni]] jezik jest kontekstno ovisan.
 
== Reference ==
*{{cite book
| author = Siniša Srbljić
| title = Jezični procesori 1
| publisher = Element
| year = 2003
| id = ISBN 953-197-129-3}}
 
{{Formalni jezici i gramatike}}
3.196

uređivanja