Razlika između inačica stranice »Kontekstno ovisni jezik«
(Bot: Automatski unos stranica) |
m (bnz) |
||
| (Nije prikazana jedna međuinačica istog suradnika) | |||
| Redak 1: | Redak 1: | ||
Kontekstno ovisni jezik''' (rjeđe još i '''jezik ovisan o sadržaju''', te '''okolinski jezik''', '''kontekstualni jezik'''<ref name="InfoRjecnik">Kiš Miroslav, ''Englesko-hrvatski i hrvatsko-engleski informatički rječnik'', Zagreb, Naklada Ljevak, 2000., str. 234</ref>) 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. | |||
== Računska svojstva == | == Računska svojstva == | ||
| Redak 21: | Redak 21: | ||
{{izvori}} | {{izvori}} | ||
*{{ | *{{Citiranje knjige | ||
| author = Siniša Srbljić | | author = Siniša Srbljić | ||
| title = Jezični procesori 1 | | title = Jezični procesori 1 | ||
Trenutačna izmjena od 12:19, 22. ožujka 2022.
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
- ↑ Kiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 234
- Siniša Srbljić (2003). Jezični procesori 1. Element. ISBN 953-197-129-3
| 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. | |||