Kontekstno zavisni jezik

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web stranice ili drugi izvori).
Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci, te nakon toga možete ukloniti ovaj šablon.

Kontekstno zavisni jezik je formalni jezik koji se može definisati kontekstno zavisnom gramatikom, koja je jedan od četiri tipa gramatika u Chomskyjevoj hijerarhiji. Najmanje je korištena od sve četiri, kako u teoriji tako i u praksi.

Računska svojstva[uredi | uredi izvor]

Računski su kontekstno zavisni jezici istovjetni linearno ograničenom nedeterminističkom Turingovom mašinom. To jest, nedeterminističkoj Turingovoj mašini sa trakom od samo kn ćelija, gdje je n veličina ulaza i k konstanta asocirana sa mašinom. Ovo znači da svaki formalni jezik kojeg takva mašina odlučuje jest kontekstno zavisni jezik, i svaki kontekstno zavisni jezik može biti odlučen takvom mašinom.

Ovaj skup jezika je također poznat kao NLIN-SPACE pošto mogu biti prihvaćeni korištenjem linearnog prostora na nedeterminističkoj Turingovoj mašini. Klasa složenosti LIN-SPACE je definisana na sličan način, osim što koristi determinističku Turingovu mašinu. 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.

Primjeri[uredi | uredi izvor]

Primjer kontekstno zavisnog jezika koji nije kontekstno nezavisan jest L = { ap : p je prost broj }. Najlakši način za ovo dokazati jest korištenjem linearno ograničene Turingove mašine.

Svojstva kontekstno zavisnih jezika[uredi | uredi izvor]

  • Unija, presjek i nadovezivanje (konkatenacija) dva kontekstno zavisna jezika jest konteksno zavisni jezik.
  • Komplement kontekstno zavisnog jezika jest i sam kontekstno zavisan.
  • Svaki kontekstno nezavisan jezik jest kontekstno zavisan.

Također pogledajte[uredi | uredi izvor]