索引式语言
编辑索引式语言是AlfredAho发现的一类形式语言；它们由索引式语法描述，可以由嵌套堆栈自动机识别。索引式语言是上下文敏感语言的一个适当的子集。它们有资格成为一个抽象的语言家族（进一步说是一个完整的AFL），因此满足许多封闭属性。然而，它们在相交或互补下是不封闭的。索引语言类在自然语言处理中具有实际的重要性，因为索引语法可以描述自然语言中出现的许多非局部约束。现在被称为线性索引语法（LIG）。相对于IG，线性索引语法有额外的限制。LIG与树状邻接语法是弱等价的（产生相同的语言类）。
索引式语言的例子
编辑以下语言是有索引的，但不是无语境的。{displaystyle{a{n}b{m}c{n}d{m}|m,ngeq0}}。这两种语言也是有索引的，但在Gazdar的表征下，甚至没有轻微的语境敏感性。{displaystyle{(ab{n}){n}|ngeq0}}。
索引式语言的属性
编辑Hopcroft和Ullman倾向于将索引语言视为一个自然类，因为它们是由几种形式主义产生的，例如。Aho的索引语法Aho的单向嵌套堆栈自动机Fischer的宏观语法Greibach的带堆栈的自动机Maibaum的代数特征Hayashi将抽水定理推广到索引语法。相反，Gilman给出了索引语言的收缩定理。
内容由匿名用户提供，本内容不代表vibaike.com立场，内容投诉举报请联系vibaike.com客服。如若转载，请注明出处：https://vibaike.com/163922/