木工刨床

[拼音]：chouxiang yuyanzu

[英文]：abstract family of languages

某些代數運算下具有封閉性的形式語言類，簡稱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不是，因為它在一般的同態對映下不封閉。