抽象語言族

在計算機科學中，特別是在形式語言理論領域，術語抽象語言族是指抽象的數學概念泛化的特徵，常見的有正則語言（正規語言），上下文無關語言和遞歸可枚舉語言以及其他形式語言，簡稱AFL，抽象語言族是用代數方法研究形式語言理論的重要成果。

基本介紹

• 中文名：抽象語言族
• 外文名：Abstract Family of Languages
• 簡寫：AFL
• 重要成果：用代數方法研究形式語言理論
• 滿三重組：同態、逆同態和與正則語言相交下
• 學科：計算機科學、形式語言理論
• 常見：正則語言、上下文無關語言

定義

某些代數運算下具有封閉性的形式語言類,簡稱AFL。抽象語言族是用代數方法研究形式語言理論的重要成果。
基本定義 　令∞為無限字母表，在其任一有限子集i上構造語言。如果任何一組語言{Li}中至少包含一個，則稱{Li}為一語言族。
在同態、逆同態和與正則語言相交下保持封閉的語言族稱為滿三重組。對並運算封閉的滿三重組稱為滿半AFL。對乘冪閉包封閉的滿半 AFL稱為滿AFL。從一個語言族出發，經上述代數運算後得到的閉包分別稱為由生成的滿三重組、滿半AFL和滿AFL,以（）、()和（）表之。如果語言族只包含一個語言L，則由生成的結構分別稱為滿主三重組,滿主半AFL及滿主AFL。如果把同態限制為無空字同態,即不得把非空字映為空字，則所有以上定義中的“滿”字皆應除去。

判別準則

把非確定型有限自動機中的輸出字母推廣為輸出字母串,所得的裝置稱為a轉換器。把一個語言L的所有語句作輸入,全體輸出語句的集合即構成新語言L′。
一個語言族成為滿三重組的充分必要條件是它在a轉換器運算下是封閉的。對。又對K≥1構造任意的。在上定義同態h為：h(c)=ε,h(ɑ)=ɑ(對任意ɑ∈)，則L中任一語句S不會比它的映像h(s)長K倍以上。因此稱h為K有界同態。所有的K有界同態統稱有界同態。
一個語言族成為 AFL的充分必要條件是它在並運算、無空字乘冪閉包、無空字正則置換、與正則語言相交及有界同態下是封閉的。
一個語言族成為滿 AFL的充分必要條件是它在並運算、乘冪閉包、正則置換、與正則語言相交及同態映射下是封閉的。
抽象接收器族 　類似於從個別的語言到抽象語言族，從個別的自動機（接收器）出發也可得到相應的抽象接收器族，簡稱AFA。AFA接受語言族有兩種方式。如果只要求該AFA最後進入終止狀態,則接受的語言族正好是滿半AFL。如果除了要求AFA進入終止狀態外，還要求它的存儲同時變空，則接受的語言族正好是滿AFL。
喬姆斯基分層的四族語言0、1、2、3都是AFL,其中只有0、2、3是滿AFL。1不是,因為它在一般的同態映射下不封閉。

正則語言

正規語言又稱正則語言是滿足下述相互等價的一組條件的一類形式語言：

可以被確定有限狀態自動機識別；

可以被非確定有限狀態自動機識別；

可以被唯讀圖靈機識別；

可以用正則表達式描述；

可以用正則文法生成。

可以用前綴文法生成。

在字母表集合Σ上的正規語言定義如下：

空集合Ø是正規語言

只包含一個空字元串的語言{ε}是正規語言

對所有，{a}是正規語言

若A, B是正規語言，，，則都是正規語言

除此之外都不是正規語言

如果一個語言不是正規語言，它需要一個記憶體至少是Ω(log log n)的自動機才能辨認。換句話說，DSPACE(o(log log n))等於所有正規語言的集合。實際上，大部分的非正規語言需要至少O(log n)的空間。

性質

正則語言的交、並、差、補運算得到的語言仍然是正則語言；

兩個正則語言連線（把第一個語言的所有字元串同第二個語言的所有字元串連線起來）後得到的語言仍然是正則語言；

正則語言閉包運算後得到的語言仍然是正則語言；

正則語言的每個字元串轉置後得到的語言仍然是正則語言；

正則語言被任意語言的字元串商（左商或右商)後得到的語言仍然是正則語言。

正則語言字元串代換後得到的語言仍然是正則語言。

與正則語言字元串同態或逆同態的語言仍然是正則語言。

語言的抽象

用代數方法描述程式設計語言, 能夠使得程式設計語言具有清晰性、層次性和可操縱性, 是對研究程式設計語言之間的聯繫的一個有益嘗試(提供語言的一個抽象模型)。具體的描述方法是: 用基調描述語言的抽象語法 , 一個基調 2= (S, F) 由它的類集 S(語言的基本語法元素)和操作集 F (語法元素間的組合關係)兩部分組成。通過引進一組語義規則, 為基調2指定語義, 也即為基調 2 所對應的語言指定語義, 這樣, 基調與引進的語義規則構成語言的一個抽象模型, 語言的這種抽象模型獨立於一個語言的具體表示。