コーン（形式言語）

形式言語理論において、錐とは、いくつかのよく知られた言語集合、特に正規言語、文脈自由言語、および再帰可算言語の族が享受する望ましい閉包特性を持つ形式言語の集合である。^[1]錐の概念は、これらすべての族を包含する、より抽象的な概念である。類似の概念に、いくぶん緩和された条件を持つ忠実錐がある。例えば、文脈依存言語は錐を形成しないが、忠実錐を形成するために必要な特性は備えている。

コーンという用語はフランス語に由来します。アメリカ向けの文献では、通常、完全なトリオについて言及されます。トリオは忠実なコーンに対応します。

円錐とは、少なくとも1つの空でない言語を含む言語族であり、あるアルファベット上の任意のものに対して、 ${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle L\in {\mathcal {S}}}$${\displaystyle \Sigma }$

• が からへの準同型である場合、言語はである。${\displaystyle h}$${\displaystyle \Sigma ^{\ast}}$${\displaystyle \Delta ^{\ast }}$${\displaystyle h(L)}$${\displaystyle {\mathcal {S}}}$
• が からへの準同型である場合、言語はである。${\displaystyle h}$${\displaystyle \Delta ^{\ast }}$${\displaystyle \Sigma ^{\ast}}$${\displaystyle h^{-1}(L)}$${\displaystyle {\mathcal {S}}}$
• が上の任意の正規言語である場合、 は の範囲内にあります。${\displaystyle R}$${\displaystyle \Sigma }$${\displaystyle L\cap R}$${\displaystyle {\mathcal {S}}}$

すべての正規言語の族は任意の円錐に含まれます。

定義を空語を導入しない準同型に制限すると、忠実な錐と呼ばれる。逆準同型は制限されない。チョムスキー階層内では、正規言語、文脈自由言語、および再帰的に可算な言語はすべて錐であるが、文脈依存言語と再帰言語は忠実な錐のみである。 ${\displaystyle \lambda}$

有限状態トランスデューサは、入力と出力の両方を持つ有限状態オートマトンです。これは、入力アルファベット上の言語を出力アルファベット上の別の言語にマッピングする変換を定義します。各コーン操作 (準同型、逆準同型、正規言語との交差) は、有限状態トランスデューサを使用して実装できます。また、有限状態トランスデューサは合成に対して閉じているため、コーン操作のすべてのシーケンスを有限状態トランスデューサで実行できます。 ${\displaystyle T}$${\displaystyle L}$${\displaystyle T(L)}$

逆に、すべての有限状態変換は錐体演算に分解できます。実際、この分解には正規形が存在し、^{[2]これは一般に}ニヴァの定理として知られています。^[3] つまり、このような各は、として効果的に分解できます 。ここで、 は準同型であり、のみに依存する正規言語です。 ${\displaystyle T}$${\displaystyle T}$${\displaystyle T(L)=g(h^{-1}(L)\cap R)}$${\displaystyle g,h}$${\displaystyle R}$${\displaystyle T}$

全体として、これは言語族が円錐であるためには、有限状態変換の下で閉じている必要があることを意味します。これは非常に強力な操作セットです。たとえば、長さが偶数である単語の秒ごとに 1 文字ずつ削除する(それ以外の場合は単語を変更しない) アルファベットを使用して、(非決定論的な) 有限状態トランスデューサを簡単に記述できます。文脈自由言語は円錐を形成するため、この特殊な操作の下で閉じています。 ${\displaystyle \{a,b\}}$${\displaystyle b}$

• 抽象言語族

• Ginsburg, Seymour; Greibach, Sheila (1967)。「言語の抽象族」。1967 年第 8 回スイッチングおよびオートマトン理論シンポジウムの会議記録、1967 年 10 月 18 ～ 20 日、テキサス州オースティン、米国。IEEE。pp. 128 ～ 139。

• ニヴァト、モーリス(1968)。 「チョムスキー言語変換」。フーリエ研究所の分析。18 (1): 339–455。土井：10.5802/aif.287。
• シーモア・ギンズバーグ『形式言語の代数的およびオートマトン理論的性質』North-Holland、1975年、ISBN 0-7204-2506-9。 
• John E. HopcroftおよびJeffrey D. Ullman、Introduction to Automata Theory, Languages, and Computation、Addison-Wesley Publishing、 Reading Massachusetts、1979 年。ISBN 0-201-02988 -X。第 11 章: 言語族の閉包特性。 
• マテスク、アレクサンドル。サロマー、アルト(1997)。 「第 4 章: 古典言語理論の側面」。グジェゴシュのローゼンベルクにて。サロマー、アルト (編)。形式言語のハンドブック。第 1 巻: 単語、言語、文法。スプリンガー・フェルラーク。 175–252ページ。ISBN 3-540-61486-9。

• 数学百科事典：Trio、Springer。