適度上下文有關語言

在形式文法理論中，適度上下文有關語言是可以有效解析但仍擁有足夠的上下文敏感性來允許自然語言的解析的一類形式語言。這個概念是 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相信這兩個類都不能窮盡適度上下文有關語言的完整集合。

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

上下文有關語言

在理論計算機科學中，上下文有關語言是可被上下文有關文法定義的形式語言。它是喬姆斯基層級中的四類文法之一。當然它在理論和實踐中都是最少使用的。

上下文有關語言的可計算性等價於線性有界非確定圖靈機。它是磁帶只有kn個單元的非確定圖靈機，這裡的n是輸入的大小而k是與這個機器關聯的常數。這意味著可以被這種機器判定的所有形式語言都是上下文有關語言，而所有上下文有關語言都可以被這種機器判定。

這種語言的集合也叫做NLIN-SPACE，因為它們可以在非確定圖靈機上使用線性空間來接受。類LIN-SPACE定義相同，除了使用確定圖靈機之外。。明顯的LIN-SPACE是NLIN-SPACE的子集，但不知道是否LIN-SPACE=NLIN-SPACE。普遍猜測它們是不相等的。