查看“︁附标语言”︁的源代码

'''附标语言'''是 [[Alfred V. Aho|Alfred Aho]] 发现的一类[[形式语言]] <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 | issn = 0004-5411 | url = http://portal.acm.org/ft_gateway.cfm?id=321488&type=pdf&coll=GUIDE&dl=GUIDE,&CFID=17841194&CFTOKEN=70113868 | access-date = 2007-10-19 | archive-date = 2019-07-13 | archive-url = https://web.archive.org/web/20190713183823/https://dl.acm.org/citation.cfm?id=321488&dl=ACM&coll=DL | dead-url = no }}</ref>；它们用[[附标文法]]描述并由[[嵌套堆栈自动机]]识别 <ref name="partee_etal_1990"> {{cite book | last = [[Barbara Partee|Partee]] | first = Barbara | coauthors = Alice ter Meulen, and Robert E. Wall | title = Mathematical Methods in Linguistics | url = https://archive.org/details/mathematicalmeth00part_561| year = 1990 | publisher = Kluwer Academic Publishers | pages = [https://archive.org/details/mathematicalmeth00part_561/page/n555 536]–542 | isbn = 978-90-277-2245-4 }} </ref>。

附标语言是[[上下文有关语言]]的真子集和[[适度上下文有关语言]]和[[上下文无关语言]]的真子集；它们在并集、[[串接]](concatenation)和[[Kleene星号]]下闭合，但在交集和补集下不闭合。Gerald Gazdar 已经依据线性附标语法特征化了适度上下文有关语言。<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 | url=https://archive.org/details/naturallanguagep00reyl | editor=U. Reyle and C. Rohrer | pages=[https://archive.org/details/naturallanguagep00reyl/page/69 69]-94}}</ref>

附标语言在[[自然语言处理]]中作为[[上下文无关语言]]的计算可承受的一般化有着实践重要性，因为[[附标文法]]可以描述自然语言中出现的很多非局部约束。
==例子==

下列语言是有附标的，但不是[[上下文无关语言|上下文无关]]的:
:<math> \{a^n b^n c^n d^n| n \geq 1 \} </math> <ref name="gazdar1998"/>

:<math> \{a^n b^m c^n d^m | m,n \geq 0 \}</math> <ref name="partee_etal_1990"/>

下面两个语言也是有附标的，但不是 Gazdar 所特征化的[[适度上下文有关语言]]:

:<math> \{a^{2^{n}} | n \geq 0 \}</math> <ref name="partee_etal_1990"/>

:<math> \{www | w \in \{a,b\}^+ \}</math> <ref name="gazdar1998"/>

在另一方面，下列语言不是有附标的 <ref> {{cite journal | last = [[Robert Gilman|Gilman]] | first = Robert | year = 1996 | title = A shrinking lemma for indexed languages | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]] | volume = 163 | issue = 1-2 | pages = 277-281 }} </ref>:
:<math>\{(a b^n)^n | n \geq 0 \}</math>

==参见==
* [[乔姆斯基谱系|乔姆斯基层级]]
* [[附标文法]]
* [[适度上下有关文法]]

==引用==
<!-- This ref will probably eventually get used, so I'm keeping it here for now
<ref name="hopcroft_ullman_1979"> {{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 = [https://archive.org/details/trent_0116301269779/page/390 390] | isbn = 020102988X}} </ref>
-->
<references/>

==外部链接==
* [https://web.archive.org/web/20070311042935/http://www.cogs.susx.ac.uk/research/nlp/gazdar/nlp-in-prolog/ch04/chapter-04-sh-1.6.3.html#sh-1.6.3 "NLP in Prolog" chapter on indexed grammars and languages]


{{形式语言与形式文法}}

[[Category:形式语言|F]]