Kontekstno ovisni jezik

Izvor: Wikipedija
Skoči na: orijentacija, traži

Kontekstno ovisni jezik (rjeđe još i jezik ovisan o sadržaju, te okolinski jezik, kontekstualni jezik[1]) je formalni jezik koji se može definirati kontekstno ovisnom 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 VE | uredi]

Računski su kontekstno ovisni jezici istovjetni linearno ograničenom nedeterminističkom 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.

Primjeri[uredi VE | uredi]

Primjer kontekstno ovisnog jezika koji nije kontekstno neovisan jest L = { ap : p je prost broj }. Najlakši način za ovo dokazati jest korištenjem linearno ograničenog Turingovog stroja.

Svojstva kontekstno ovisnih jezika[uredi VE | uredi]

  • Unija, presjek i nadovezivanje (konkatenacija) dva kontekstno ovisna jezika jest konteksno ovisni jezik.
  • Komplement kontekstno ovisnog jezika jest i sam kontekstno ovisan.
  • Svaki kontekstno neovisni jezik jest kontekstno ovisan.

Izvori[uredi VE | uredi]

  1. Kiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 234
Teorija automata: formalni jezici i formalne gramatike
Chomskyjeva
hijerarhija
Gramatike Jezici Minimalni
automat
Tip 0 Neograničenih produkcija Rekurzivno prebrojiv Turingov stroj
n/a (nema uobičajenog imena) Rekurzivni Odlučitelj
Tip 1 Kontekstno ovisna Kontekstno ovisni Linearno ograničen
n/a Indeksirana Indeksirani Ugniježđenog stoga
Tip 2 Kontekstno neovisna Kontekstno neovisni Nedeterministički potisni
n/a Deterministička kontekstno neovisna Deterministički kontekstno neovisni Deterministički potisni
Tip 3 Regularna Regularni Konačni
Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije.