附標語言

附標語言是 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