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:

[2]

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]

Vidjeti također

uredi

Izvori

uredi
  1. Aho, Alfred. 1968. Indexed grammars—an extension of context-free grammars. Journal of the ACM. 15 (4): 647–671
  2. Hopcroft, John; Ullman, Jeffrey. 1979. Introduction to automata theory, languages, and computation. Addison-Wesley. str. 390
  3. Partee, Barbara; ter Meulen, Alice; Wall, Robert E. 1990. Mathematical Methods in Linguistics. Kluwer Academic Publishers. str. 536–542

Vanjske poveznice

uredi
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.