Toggle menu
309,3 tis.
61
18
533,3 tis.
Hrvatska internetska enciklopedija
Toggle preferences menu
Toggle personal menu
Niste prijavljeni
Your IP address will be publicly visible if you make any edits.

Kontekstno ovisni jezik: razlika između inačica

Izvor: Hrvatska internetska enciklopedija
Bot: Automatski unos stranica
 
m Bot: Automatska zamjena teksta (-{{cite book +{{Citiranje knjige)
Redak 21: Redak 21:
{{izvori}}
{{izvori}}


*{{cite book
*{{Citiranje knjige
  | author = Siniša Srbljić
  | author = Siniša Srbljić
  | title = Jezični procesori 1
  | title = Jezični procesori 1

Inačica od 17. studeni 2021. u 05:23

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

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

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

  • 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

  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.