Indeksirani jezik: razlika između inačica
m Bot: Automatska zamjena teksta (-{{cite book +{{Citiranje knjige) |
m brisanje nepotrebnog teksta |
||
Redak 1: | Redak 1: | ||
'''Indeksirani jezik''' je [[formalni jezik]] kojeg je otkrio [[Alfred Aho]], i koji je pravi [[podskup]] skupa svih [[kontekstno ovisni jezik|kontekstno ovisnih jezika]] i pravi nadskup skupa svih [[kontekstno neovisni jezik|kontekstno neovisnih jezika]].<ref> {{cite journal | last = [[Alfred Aho|Aho]] | first = Alfred | year = 1968 | title = Indexed grammars—an extension of context-free grammars | journal = [[Journal of the ACM]] | volume = 15 | issue = 4 | pages = 647–671 }} </ref> Indeksirani jezici mogu biti oblika: | |||
:<math> L = \{a^n b^n c^n | n \geq 1 \} </math> <ref> {{Citiranje knjige | last = [[John Hopcroft|Hopcroft]] | first = John | coauthors = [[Jeffrey Ullman]] | title = [[Introduction to automata theory, languages, and computation]] | year = 1979 | publisher = Addison-Wesley | pages = 390 }} </ref> | :<math> L = \{a^n b^n c^n | n \geq 1 \} </math> <ref> {{Citiranje knjige | last = [[John Hopcroft|Hopcroft]] | first = John | coauthors = [[Jeffrey Ullman]] | title = [[Introduction to automata theory, languages, and computation]] | year = 1979 | publisher = Addison-Wesley | pages = 390 }} </ref> |
Posljednja izmjena od 8. ožujak 2022. u 07:59
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 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đer
Izvori
- ↑ Aho, Alfred (1968). "Indexed grammars—an extension of context-free grammars". Journal of the ACM 15 (4): 647–671
- ↑ Hopcroft, John; Jeffrey Ullman (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. str. 390
- ↑ Partee, Barbara; Alice ter Meulen, and Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. str. 536–542
Vanjske poveznice
Nedovršeni članak Indeksirani jezik koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima uređivanja Hrvatske internetske enciklopedije.
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. |