Indeksirani jezik
Indeksirani jezik je formalni jezik kojeg je otkrio Alfred Aho, i koji je pravi podskup skupa svih kontekstno ovisnih jezika i pravi nadskup skupa svih kontekstno neovisnih jezika.[1] Indeksirani jezici mogu biti oblika:
Minimalna gramatika koja generira indeksirani jezik jest indeksirana gramatika, a automat koji ga prihvaća jest automat s ugniježđenim stogom. Indeksirana gramatika može imati stog pridodan nezavršnim znakovima koji se kopiraju u nezavršne znakove kćeri. Pored dodavanja i uzimanja znakova sa stoga, automat s ugniježđenim stogom može i čitati sadržaj stoga. Također, stog može ugnijezditi druge stogove unutar sebe.[3]
- ↑ Aho, Alfred. 1968. Indexed grammars—an extension of context-free grammars. Journal of the ACM. 15 (4): 647–671
- ↑ Hopcroft, John; Ullman, Jeffrey. 1979. Introduction to automata theory, languages, and computation. Addison-Wesley. str. 390
- ↑ Partee, Barbara; ter Meulen, Alice; Wall, Robert E. 1990. Mathematical Methods in Linguistics. Kluwer Academic Publishers. str. 536–542
Nedovršeni članak Indeksirani jezik koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima Wikipedije.
| 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. | |||