Индексиран језик — разлика између измена
Садржај обрисан Садржај додат
м ispravke |
м Literatura |
||
Ред 1:
'''Индексирани језици''' су класа [[формални језик|формалних језика]] које је открио [[Алфред Ахо]]<ref name="aho1968"> {{cite journal | last = [[Алфред Ахо|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 | url = http://portal.acm.org/ft_gateway.cfm?id=321488&type=pdf&coll=GUIDE&dl=GUIDE,&CFID=17841194&CFTOKEN=70113868 | doi = 10.1145/321479.321488 }}
Индексирани језици представљају прави [[подскуп]] скупа [[контекстно-сензитивни језик|контекстно-сензитивних језика]] и прави надскуп скупова [[благо контекстно-сензитивни језик|благо контекстно-сензитивних језика]] и [[контекст-слободни језик|контекстно-слободних језика]]. Квалификују се као [[апстрактна фамилија језика]] и стога задовољавају многа својства затворења. Међутим, они нису затворени у односу на пресек или комплемент.<ref name="aho1968"/> Џералд Газдар је карактерисао благо контекстно-сензитивне језике преко линеарних индексираних граматика.<ref name="gazdar1998">{{cite book | chapter=Applicability of Indexed Grammars to Natural Languages | year=1988 | last=Gazdar | first=Gerald | title=Natural Language Parsing and Linguistic Theories | editor=U. Reyle and C. Rohrer | pages=69–94}}</ref>
Ред 17:
:<math> \{www | w \in \{a,b\}^+ \}</math><ref name="gazdar1998"/>
Са друге стране, следећи језик није индексиран<ref> {{cite journal | last = [[Роберт Гилман|Gilman]] | first = Robert | year = 1996 | title = A shrinking lemma for indexed languages | journal = Theoretical Computer Science | volume = 163 | issue = 1-2 | pages = 277–281 | doi = 10.1016/0304-3975(96)00244-7 }}
:<math>\{(a b^n)^n | n \geq 0 \}</math>
| |||