Kontekstno ovisni jezik: razlika između inačica
m robot Dodaje: bs:Kontekstno zavisni jezik |
+ref |
||
Redak 1: | Redak 1: | ||
'''Kontekstno ovisni jezik''' 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. |
'''Kontekstno ovisni jezik''' 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čunski su kontekstno ovisni jezici istovjetni linearno ograničenom nedeterminističkom [[Turingov stroj|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. |
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. |
||
Redak 16: | Redak 16: | ||
* Komplement kontekstno ovisnog jezika jest i sam kontekstno ovisan. |
* Komplement kontekstno ovisnog jezika jest i sam kontekstno ovisan. |
||
* Svaki [[kontekstno neovisni jezik|kontekstno neovisni]] jezik jest kontekstno ovisan. |
* Svaki [[kontekstno neovisni jezik|kontekstno neovisni]] jezik jest kontekstno ovisan. |
||
== Reference == |
|||
*{{cite book |
|||
| author = Siniša Srbljić |
|||
| title = Jezični procesori 1 |
|||
| publisher = Element |
|||
| year = 2003 |
|||
| id = ISBN 953-197-129-3}} |
|||
{{Formalni jezici i gramatike}} |
{{Formalni jezici i gramatike}} |
Inačica od 23. ožujka 2007. u 19:49
Kontekstno ovisni jezik 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.
Reference
- 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. |