附标语言
维基百科,自由的百科全书
附标语言是 Alfred Aho 发现的一类形式语言 [1];它们用附标文法描述并由嵌套堆栈自动机识别 [2]。
附标语言是上下文有关语言的真子集和适度上下文有关语言和上下文无关语言的真子集;它们在并集、串接(concatenation)和Kleene星号下闭合,但在交集和补集下不闭合。Gerald Gazdar 已经依据线性附标语法特征化了适度上下文有关语言。[3]
附标语言在自然语言处理中作为上下文无关语言的计算可承受的一般化有着实践重要性,因为附标文法可以描述自然语言中出现的很多非局部约束。
目录 |
[编辑] 例子
下列语言是有附标的,但不是上下文无关的:
下面两个语言也是有附标的,但不是 Gazdar 所特征化的适度上下文有关语言:
在另一方面,下列语言不是有附标的 [4]:
[编辑] 参见
[编辑] 引用
- ^ Aho, Alfred(1970年).“Indexed grammars—an extension of context-free grammars”.Journal of the ACM.15(4):647–671.
- ^ 2.0 2.1 2.2 Partee, Barbara,Alice ter Meulen, and Robert E. Wall(1990).Mathematical Methods in Linguistics.Kluwer Academic Publishers,536–542.ISBN 978-90-277-2245-4.
- ^ 3.0 3.1 3.2 Gazdar, Gerald(1988).“Applicability of Indexed Grammars to Natural Languages”,U. Reyle and C. Rohrer 编:Natural Language Parsing and Linguistic Theories,69-94.
- ^ Gilman, Robert(1996年). “A shrinking lemma for indexed languages”.Theoretical Computer Science.163(1-2):277-281.
[编辑] 外部链接
自动机理论: 形式语言和形式文法 | |||
---|---|---|---|
乔姆斯基层级 | 文法 | 语言 | 极小自动机 |
类型 0 | 无限制 | 递归可枚举 | 图灵机 |
n/a | (无公用名) | 递归 | 判定器 |
类型 1 | 上下文有关 | 上下文有关 | 线性有界 |
n/a | 附标 | 附标 | 嵌套堆栈 |
n/a | 树-邻接 | 适度上下文有关 | 嵌入下推 |
类型 2 | 上下文无关 | 上下文无关 | 非确定下推 |
n/a | 确定上下文无关 | 确定上下文无关 | 确定下推 |
类型 3 | 正则 | 正则 | 有限 |
每个语言或文法范畴都是其直接上面的范畴的真子集。 |