Otvori glavni izbornik

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 sa 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 sa ugniježđenim stogom može i čitati sadržaj stoga. Također, stog može ugnijezditi druge stogove unutar sebe. [3]

Vidjeti takođerUredi

IzvoriUredi

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

Vanjske povezniceUredi