パターン言語（形式言語）

理論計算機科学において、パターン言語は定数と変数の文字列のすべての特定のインスタンスの集合として定義できる形式言語です。パターン言語は機械学習の文脈でダナ・アングルインによって導入されました。^[1]

定数記号の有限集合 Σと、 Σ と交わらない変数記号の可算集合X が与えられたとき、パターンはΣ∪ Xの有限の空でない記号列である。パターンpの長さは、| p | で表され、その記号の数に等しい。n個の異なる変数（それぞれが複数回出現してもよい）を含むすべてのパターンの集合はP _nで表され、すべてのパターンの集合はP _*で表される。置換は、写像f : P _* → P _*であり、^{[注 1]}

• f は文字列連結(⋅)に関する準同型であり、形式的には: ∀ p , q ∈ P _* . f ( p ⋅ q ) = f ( p )⋅ f ( q );
• f は非消去であり、正式には: ∀ p ∈ P _* . f ( p ) ≠ ε、ここで ε は空の文字列を表す。
• f は定数を尊重します。正式には: ∀ s ∈Σ. f ( s ) = s .

あるパターンp、q ∈ P _*およびある置換fに対してp = f ( q ) である場合、p はqよりも一般性が低いと言われ、 p ≤ qと書きます。その場合、必然的に | p | ≥ | q | が成り立ちます。パターンpの場合、その言語は定数のみから構築されるすべての一般性が低いパターンの集合として定義され、正式にはL ( p ) = { s ∈ Σ ⁺  : s ≤ p } です。ここで、Σ ^{+ は}Σ のすべての有限の空でない記号文字列の集合を表します。

たとえば、定数 Σ = {0, 1} と変数X = { x、y、z、...} を使用すると、パターン 0 x 10 xx 1 ∈ P ₁とxxy ∈ P ₂の長さはそれぞれ 7 と 3 になります。前者のパターンのインスタンスは 00 z 100 z 0 z 1 と 01 z 101 z 1 z 1 で、 x をそれぞれ0 zと 1 zにマッピングし、他の各シンボルをそれ自体にマッピングする置換によって取得されます。 00 z 100 z 0 z 1 と 01 z 101 z 1 z 1 はどちらもxxyのインスタンスでもあります。実際、L (0 x 10 xx 1) はL ( xxy )のサブセットです。パターンx 0 とx 1 の言語は、それぞれ偶数と奇数の2 進数を表すすべてのビット文字列の集合です。xxの言語は、ビット文字列をそれ自体と連結することによって得られるすべての文字列の集合です。例：00、11、0101、1010、11101110 ∈ L ( xx )。

任意の文字列s ∈ Σ ⁺とパターンpに対してs ∈ L ( p )であるかどうかを決定する問題はNP 完全であり（図を参照）、したがって任意のパターンp、qに対してp ≤ qであるかどうかを決定する問題も NP 完全である。^[2]

パターン言語のクラスは... の下では 閉じられていません。

• 和集合: 例えば上記のようにΣ = {0,1}の場合、L (01)∪L (10)はパターン言語ではない。
• 補語: Σ ⁺ \ L (0) はパターン言語ではありません。
• 共通部分: L ( x 0 y )∩ L ( x 1 y ) はパターン言語ではありません。
• クリーネプラス：L（0）^+はパターン言語ではありません。
• 準同型性：f ( L ( x )) = L (0) ⁺はパターン言語ではない（f (0) = 0 = f (1)と仮定）。
• 逆準同型: f (0) = 1、f (1) = 11と仮定すると、 f ⁻¹ (111) = { 01, 10, 000 }はパターン言語ではない。

パターン言語のクラスは... の下で 閉じられています。

• 連結: L ( p )⋅ L ( q ) = L ( p ⋅ q );
• 反転：^L ( p ) rev ⁼ L ( prev )。^[3]

p、q ∈ P ₁がちょうど 1 つの変数を含むパターンである場合、 L ( p ) ⊆ L ( q )の場合にのみp ≤ q が成り立ちます。パターンの長さが等しい場合にも同じ同値性が成り立ちます。^[4] 異なる長さのパターンの場合、上記の例p = 0 x 10 xx 1 およびq = xxy は、 p ≤ qを意味することなくL ( p ) ⊆ L ( q ) が成立する可能性があることを示しています。ただし、任意の長さの任意の 2 つのパターンpとqは、一貫した変数名の変更を除いて等しい場合に限り、同じ言語を生成します。^[5] 各パターンp は、(⋅) の結合性を法として、生成された言語L ( p )のすべての文字列の共通の一般化です。

洗練されたチョムスキー階層では、パターン言語のクラスは、それぞれシングルトン^[注2]とインデックス言語の適切なスーパークラスとサブクラスですが、その間の言語クラスとは比較できません。後者のため、パターン言語クラスは以下の表に明示的に示されていません。

パターン言語のクラスは、有限言語のクラス、正規言語のクラス、文脈自由言語のクラスとは比較できません。

• パターン言語L ( xx )は、ポンピング補題により文脈自由ではない（したがって、正則でも有限でもない） 。
• 有限な（したがって正規かつ文脈自由でもある）言語 { 01, 10 } はパターン言語ではない。

各シングルトン言語は、変数のないパターンによって生成されるパターン言語です。

各パターン言語は、インデックス付き文法によって生成できます。たとえば、Σ = { a、b、c } およびX = { x、y } を使用すると、パターンa x b y c x a y bは、非終端記号N = { S _x、S _y、S } ∪ X、終端記号T = Σ、インデックス記号F = { a _x、b _x、c _x、a _y、by _y、c _y }、開始記号S _x、および次の生成規則を持つ文法によって生成されます。

導出例は次のとおりです。

S _{x [} ]   ⇒   S _x [ b _x ]   ⇒   S _x [ a _x b _x ]   ⇒   S _y [ a _x b _x ]   ⇒   S _y [ c _y a _x b _x ]   ⇒   S [ c _y a _x b _x ]   ⇒   a x [ c _y a _x b _x ] b y [ c _y a _x b _x ] c x [ c _y a _x b _x ] a y [ c _y a _x b _x ] b   ⇒   a x [ a _x b _x ] b y [ c _y a _x b _x ] c x [ c _y a _x b _x ] a y [ c _y a _x b _x ] b   ⇒   a a b x [ _] b y [ c _y a _x b _x ] c x [ c _y a _x b _x ] a y [ c y a _x b _x ] b   ⇒   a ab x [ ] b y [ c _y a _x b _x ] c x [ c _y a _x b _x ] a y [ c _y a _x b _x ] b   ⇒   a ab b y [ c _y a _x b _x ] c x [ c _y a _x b _x ] a y [ c _y a _x b _x ] b   ⇒   ... ⇒ a ab b c y [ ] c x [ c _y a _x b _x ] a y [ c _y a _x b _x ] b   ⇒   a ab b c c ab x [ ] a y [ c _y a _x b _x ] b   ⇒   ...   ⇒   a ab b c c ab _x [ ] a y [ c _y a _x b _x ] _b ⇒ ... ⇒ a ab b c c ab a c y [ ] b _{⇒ a ab} b c c ab   a   c _b​​​​​​​   ​   ​ ​ ​ ​ ​ ​

同様に、任意のパターンからインデックス文法を構築できます。

文字列のサンプルセットSが与えられた場合、パターンp はS ⊆ L ( p ) であればSを記述的といいますが、それ以外のパターンqではS ⊆ L ( q ) ⊂ L ( p ) ではありません。

任意のサンプルセットSが与えられた場合、 Sの記述パターンは次のように計算できる。

• S内の最短文字列より長くないすべてのパターン（変数名の変更まで）を列挙する。
• それらからSのスーパーセットを生成するパターンを選択し、
• それらから最大の長さのパターンを選択し、
• それらの中から≤に関して最小となるパターンを選択する。^[6]

このアルゴリズムに基づいて、パターン言語のクラスは正の例から極限的に識別することができます。 ^[7]