附標語言

附標語言是 Alfred Aho 發現的一類形式語言 ；它們用附標文法描述並由嵌套堆疊自動機識別 。

簡介

附標語言是上下文有關語言的真子集和適度上下文有關語言和上下文無關語言的真子集；它們在並集、串接(concatenation)和Kleene星號下閉合，但在交集和補集下不閉合。Gerald Gazdar 已經依據線性附標語法特徵化了適度上下文有關語言。

附標語言在自然語言處理中作為上下文無關語言的計算可承受的一般化有著實踐重要性，因為附標文法可以描述自然語言中出現的很多非局部約束。

例子

下列語言是有附標的，但不是上下文無關的:

下面兩個語言也是有附標的，但不是 Gazdar 所特徵化的適度上下文有關語言:

在另一方面，下列語言不是有附標的:

嵌套堆疊自動機

在自動機理論中，嵌套堆疊自動機是可以利用持有作為附加棧的數據的棧的有限自動機。嵌套堆疊自動機除了壓入和彈出外還可以讀它的棧。嵌套堆疊自動機有能力識別附標語言。

附標文法

附標文法是描述附標語言的形式文法。它們有三個無交集的符號集合: 普通終結符、非終結符和只出現在中間推導中的附標(index)的集合。產生式可以如上下文無關文法那樣把一個非終結符替代為終結符和非終結符的字元串，但是它還把非終結符替代為跟隨著一個附標的非終結符，把跟隨著一個附標的非終結符替代為非終結符。

附標只可以出現在非終結符之後或其他附標之後，所以所有非終結符都可以被看作跟隨它之後的這些附標的所有者，它們形成了一個棧(產生式在非終結符之後增加或去除附標)。

實際上，附標的棧可以計數並記住套用了和以何種次序套用了什麼規則。