附标语言

附标语言是 Alfred Aho 发现的一类形式语言 ^[1]；它们用附标文法描述并由嵌套堆栈自动机识别 ^[2]。

附标语言是上下文有关语言的真子集和适度上下文有关语言和上下文无关语言的真子集；它们在并集、串接(concatenation)和Kleene星号下闭合，但在交集和补集下不闭合。Gerald Gazdar 已经依据线性附标语法特征化了适度上下文有关语言。^[3]

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

例子

下列语言是有附标的，但不是上下文无关的:

${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n\geq 1\}}$ ^[3]

${\displaystyle \{a^{n}b^{m}c^{n}d^{m}|m,n\geq 0\}}$ ^[2]

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

${\displaystyle \{a^{2^{n}}|n\geq 0\}}$ ^[2]

${\displaystyle \{www|w\in \{a,b\}^{+}\}}$ ^[3]

在另一方面，下列语言不是有附标的 ^[4]:

${\displaystyle \{(ab^{n})^{n}|n\geq 0\}}$

参见

• 乔姆斯基层级
• 附标文法
• 适度上下有关文法

引用

1. Aho, Alfred. Indexed grammars—an extension of context-free grammars. Journal of the ACM. 1968, 15 (4): 647–671 [2007-10-19]. ISSN 0004-5411. （原始内容存档于2019-07-13）.
2. Partee, Barbara; Alice ter Meulen, and Robert E. Wall. Mathematical Methods in Linguistics. Kluwer Academic Publishers. 1990: 536–542. ISBN 978-90-277-2245-4. 引文使用过时参数coauthors (帮助)
3. Gazdar, Gerald. Applicability of Indexed Grammars to Natural Languages. U. Reyle and C. Rohrer (编). Natural Language Parsing and Linguistic Theories. 1988: 69-94.
4. Gilman, Robert. A shrinking lemma for indexed languages. Theoretical Computer Science. 1996, 163 (1-2): 277–281.

外部链接

• "NLP in Prolog" chapter on indexed grammars and languages