適度上下文有關語言

在形式文法理論中，適度上下文有關語言是可以有效解析但仍擁有足夠的上下文敏感性來允許自然語言的解析的一類形式語言。這個概念是 Aravind Joshi 在1985年首次介入的。

此語言類的形式條件有:

1: 語言必須是在多項式時間內可解析的。

2: 語言必須有恆定增長；這意味着字符串長度的分佈應當是線性的而非上線性(supralinear)的。這通常由證明某類適度上下文有關語言的泵引理來保證。

3: 語言應當容許有限的跨序列依賴(cross-serial dependencies)，允許在兩個任意長子短語之間施加文法協定；上下文無關文法不滿足這個條件。要求由與自身相串接的字符串所構成的語言屬於適度上下文有關語言在形式上確保了這個條件。

在建立適度上下文有關語言公式化上的一些嘗試包括 D. J. Weir 開發的線性上下文無關重寫系統，Edward P. Stabler 的極小主義者文法，Carl Pollard 的頭文法，Mark Steedman 開發的組合範疇文法， Gerald Gazdar 定義的線性附標文法，Aravind Joshi 開發的樹-鄰接文法。前兩個文法類定義同樣的語言集合，而餘下的定義一個單一的、嚴格更小的語言類；儘管在兩個類中所有語言都是適度上下文有關的並且兩個類都支持某種跨序列依賴，Laura Kallmeyer 相信這兩個類都不能窮盡適度上下文有關語言的完整集合。

大量的上述的類可以用線索自動機來解析，而更小的類可以用嵌入下推自動機來解析。

參見[編輯]

進一步閱讀[編輯]

Joshi, Aravind; Vijay-Shanker, K.; Weir, David, The Convergence of Mildly Context-Sensitive Grammar Formalisms, Sells, Peter; Shieber, Stuart; Wasow, Thomas (編), Foundational Issues in Natural Language Processing, Cambridge, MA: MIT Press: 31–81, 1991 [2007-10-19], ISBN 0-262-19303-5, （原始內容存檔於2020-10-22） .

Vijay-Shanker, K.; Weir, David, The Equivalence of Four Extensions of Context-Free Grammars, Mathematical Systems Theory, 1994, 27 (6): 511–546 [2007-10-19], ISSN 0025-5661, （原始內容存檔於2005-08-24） .

外部連結[編輯]