Kontekstno zavisni jezik
From Wikipedia, the free encyclopedia
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.
 | Ovaj članak ili neki od njegovih odlomaka nije dovoljno potkrijepljen izvorima (literatura, veb-sajtovi ili drugi izvori). |
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.
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.
- 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.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
