Indeksirani jezik: razlika između inačica

Inačica od 17. studeni 2021. u 03:20

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:

L=\{a^{n}b^{n}c^{n}|n\geq 1\}

^[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đer

Chomskyjeva hijerarhija

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

"NLP in Prolog" poglavlje o indeksiranim gramatikama i jezicima

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.

[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. Addison-Wesley. str. 390

[3] Partee, Barbara; Alice ter Meulen, and Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. str. 536–542

[1]

[2]

[3]

@@ Redak 1: / Redak 1: @@
 <!--'''Indeksirani jezik'''-->'''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> {{cite book | 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>
-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 [[završni i nezavršni znakovi|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. <ref> {{cite book | last = [[Barbara Partee|Partee]] | first = Barbara | coauthors = Alice ter Meulen, and Robert E. Wall | title = Mathematical Methods in Linguistics | year = 1990 | publisher = Kluwer Academic Publishers | pages = 536–542 }} </ref>
+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 [[završni i nezavršni znakovi|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. <ref> {{Citiranje knjige | last = [[Barbara Partee|Partee]] | first = Barbara | coauthors = Alice ter Meulen, and Robert E. Wall | title = Mathematical Methods in Linguistics | year = 1990 | publisher = Kluwer Academic Publishers | pages = 536–542 }} </ref>
 == Vidjeti također ==