Kontekstno ovisni jezik: razlika između inačica

'''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.

 

 

 

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.

 

{{Formalni jezici i gramatike}}