抽象言語族

コンピュータサイエンス、特に形式言語理論の分野において、抽象言語族とは、正規言語、文脈自由言語、再帰的に列挙可能な言語、および科学文献で研究されている他の形式言語族に共通する特性を一般化する抽象的な数学的概念です。

形式言語とは、抽象記号Σの有限集合が存在する集合Lであり、* はクリーネのスター演算です。 ${\displaystyle L\subseteq \Sigma ^{*}}$

言語族とは、順序付けられたペアであり、 ${\displaystyle (\Sigma ,\Lambda )}$

1. Σ は無限の記号の集合です。
2. Λ は形式言語の集合です。
3. Λ内の各Lに対して、次のような有限部分集合が存在する。${\displaystyle \Sigma _{1}\subseteq \Sigma }$${\displaystyle L\subseteq \Sigma _{1}^{*}}$
4. Λ内の何らかのLに対してL ≠ Ø となる。

トリオは、空語、逆準同型、および正規言語との交差を 導入しない準同型に対して閉じた言語の族です。

完全トリオは、円錐とも呼ばれ 、任意の準同型で閉じたトリオです。

（完全な）セミ AFL は、ユニオンの下で閉じられた（完全な）トリオです。

(完全) AFL は、連結とクリーネプラスに関して閉じた(完全) 半 AFLです。

以下は抽象的な言語族の研究から得られたいくつかの簡単な結果である。^[1]

チョムスキー階層では、正規言語、文脈自由言語、再帰的可算言語はすべて完全な AFL です。ただし、文脈依存言語と再帰言語は AFL ですが、任意の準同型に対して閉じていないため、完全な AFL ではありません。

正規言語族は任意の円錐（フルトリオ）内に含まれます。抽象族の他のカテゴリは、シャッフル、反転、置換などの他の操作による閉包によって識別できます。^[2]

南カリフォルニア大学のシーモア・ギンズバーグとハーバード大学のシーラ・グライバッハは、 1967年にIEEE第8回スイッチングおよびオートマトン理論シンポジウムで最初のAFL理論論文を発表しました。 ^[3]

• Ginsburg, Seymour; Greibach, Sheila (1967)。「言語の抽象族」。1967 年第 8 回スイッチングおよびオートマトン理論シンポジウムの会議記録、1967 年 10 月 18 ～ 20 日、テキサス州オースティン、米国。IEEE。pp. 128 ～ 139。
• シーモア・ギンズバーグ『形式言語の代数的およびオートマトン理論的性質』North-Holland、1975年、ISBN 0-7204-2506-9。 
• John E. Hopcroft および Jeffrey D. Ullman著『オートマトン理論、言語、計算入門』Addison-Wesley Publishing、マサチューセッツ州リーディング、1979 年。ISBN 0-201-02988 -X。第 11 章: 言語族の閉包特性。 
• マテスク、アレクサンドル。サロマー、アルト (1997)。 「第 4 章: 古典言語理論の側面」。グジェゴシュのローゼンベルクにて。サロマー、アルト (編)。形式言語のハンドブック。第 1 巻: 単語、言語、文法。スプリンガー・フェルラーク。 175–252ページ。ISBN 3-540-61486-9。