Operations in formal language theory
コンピュータサイエンスの 形式言語理論 の分野では 、 様々な 文字列関数が頻繁に用いられます。しかし、その表記法は コンピュータプログラミング で使用される表記法とは異なり 、理論分野でよく用いられる関数の中には、プログラミングではほとんど用いられないものもあります。この記事では、これらの基本用語のいくつかを定義します。
文字列と言語 文字列は有限個の文字の並びです。 空文字列 は で表されます 。2つの文字列 と を連結したもの は 、あるいは短縮して で 表されます 。空文字列との連結には違いはありません: 。文字列の連結は のように結合的 です: 。 ε {\displaystyle \varepsilon } s {\displaystyle s} t {\displaystyle t} s ⋅ t {\displaystyle s\cdot t} s t {\displaystyle st} s ⋅ ε = s = ε ⋅ s {\displaystyle s\cdot \varepsilon =s=\varepsilon \cdot s} s ⋅ ( t ⋅ u ) = ( s ⋅ t ) ⋅ u {\displaystyle s\cdot (t\cdot u)=(s\cdot t)\cdot u}
例えば、 。 ( ⟨ b ⟩ ⋅ ⟨ l ⟩ ) ⋅ ( ε ⋅ ⟨ a h ⟩ ) = ⟨ b l ⟩ ⋅ ⟨ a h ⟩ = ⟨ b l a h ⟩ {\displaystyle (\langle b\rangle \cdot \langle l\rangle )\cdot (\varepsilon \cdot \langle ah\rangle )=\langle bl\rangle \cdot \langle ah\rangle =\langle blah\rangle }
言語 と は、有限または無限の文字列の集合です。和集合、積集合などの通常の集合演算に加えて、言語には連結を適用できます。とが両方 とも 言語である場合、それらの連結は、 の任意の文字列 と の任意の文字列 の連結の集合として定義され 、正式にはとなります 。ここでも、連結ドットは 簡潔にするために省略されることがよくあります。 S {\displaystyle S} T {\displaystyle T} S ⋅ T {\displaystyle S\cdot T} S {\displaystyle S} T {\displaystyle T} S ⋅ T = { s ⋅ t ∣ s ∈ S ∧ t ∈ T } {\displaystyle S\cdot T=\{s\cdot t\mid s\in S\land t\in T\}} ⋅ {\displaystyle \cdot }
空文字列のみからなる 言語は、空言語 と区別する必要があります 。前者を任意の言語に連結しても変化はありません: です が、後者を連結すると常に空言語 が生成されます: 。言語の連結は結合的です: 。 { ε } {\displaystyle \{\varepsilon \}} { } {\displaystyle \{\}} S ⋅ { ε } = S = { ε } ⋅ S {\displaystyle S\cdot \{\varepsilon \}=S=\{\varepsilon \}\cdot S} S ⋅ { } = { } = { } ⋅ S {\displaystyle S\cdot \{\}=\{\}=\{\}\cdot S} S ⋅ ( T ⋅ U ) = ( S ⋅ T ) ⋅ U {\displaystyle S\cdot (T\cdot U)=(S\cdot T)\cdot U}
例えば、 を省略すると 、3桁の10進数全体の集合は となります 。任意の長さの10進数全体の集合は、無限言語の一例です。 D = { ⟨ 0 ⟩ , ⟨ 1 ⟩ , ⟨ 2 ⟩ , ⟨ 3 ⟩ , ⟨ 4 ⟩ , ⟨ 5 ⟩ , ⟨ 6 ⟩ , ⟨ 7 ⟩ , ⟨ 8 ⟩ , ⟨ 9 ⟩ } {\displaystyle D=\{\langle 0\rangle ,\langle 1\rangle ,\langle 2\rangle ,\langle 3\rangle ,\langle 4\rangle ,\langle 5\rangle ,\langle 6\rangle ,\langle 7\rangle ,\langle 8\rangle ,\langle 9\rangle \}} D ⋅ D ⋅ D {\displaystyle D\cdot D\cdot D}
文字列のアルファベット 文字列のアルファベット と は、特定の文字列に現れるすべての文字の集合である。s が 文字列である場合、その アルファベット は次のように表される。
Alph ( s ) {\displaystyle \operatorname {Alph} (s)} 言語のアルファベット は 、 の任意の文字列に出現するすべての文字の集合であり 、正式には です 。 S {\displaystyle S} S {\displaystyle S} Alph ( S ) = ⋃ s ∈ S Alph ( s ) {\displaystyle \operatorname {Alph} (S)=\bigcup _{s\in S}\operatorname {Alph} (s)}
たとえば、セットは 文字列 のアルファベットであり 、上記は 上記の言語のアルファベットである だけでなく、すべての 10 進数の言語のアルファベットでもあります。 { ⟨ a ⟩ , ⟨ c ⟩ , ⟨ o ⟩ } {\displaystyle \{\langle a\rangle ,\langle c\rangle ,\langle o\rangle \}} ⟨ c a c a o ⟩ {\displaystyle \langle cacao\rangle } D {\displaystyle D} D ⋅ D ⋅ D {\displaystyle D\cdot D\cdot D}
文字列の置換 Lを 言語 とし 、 Σをそのアルファベットとする。 文字列置換 、あるいは単に 置換とは 、Σの文字を（異なるアルファベットの場合もある）言語に写像する写像 f である。例えば、文字 a∈Σが与えられたとき、 f ( a )= La が成り立つ 。 ここで、 La⊆Δ * は アルファベットがΔである言語である。この写像は文字列にも拡張でき 、
f (ε)=ε 空文字列 εの場合 、
f ( sa ) = f ( s ) f ( a ) 文字列s ∈ L と文字 a ∈ Σに対して 。文字列の置換は言語全体に拡張できる。 [1]
f ( L ) = ⋃ s ∈ L f ( s ) {\displaystyle f(L)=\bigcup _{s\in L}f(s)} 正規言語は 文字列置換に対して閉じている。つまり、正規言語のアルファベットの各文字を別の正規言語に置き換えても、結果は依然として正規言語である。 [2] 同様に、 文脈自由言語は 文字列置換に対して閉じている。 [3] [注 1]
簡単な例としては、 f uc (.) を大文字に変換することが挙げられます。これは次のように定義できます。
キャラクター 言語にマッピング 述べる × 関数 uc ( x ) ‹ a › { ‹ A › } 小文字を対応する大文字にマッピングする ‹ あ › { ‹ A › } 大文字をそれ自身にマッピングする ‹ ß › { ‹ SS › } 大文字は使用できません。2文字の文字列にマップします。 ‹0› { ε } 数字を空の文字列にマッピングする ‹!› { } 句読点を禁止し、空の言語にマップする ... 他の文字についても同様
f uc を文字列に拡張すると 、例えば
f uc (‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹STRASSE›}, f uc (‹u2›) = {‹U›} ⋅ {ε} = {‹U›}、そして f uc (‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}。 f uc を言語に拡張すると 、例えば
f uc ({ ‹Straße›, ‹u2›, ‹Go!› }) = { ‹STRASSE› } ∪ { ‹U› } ∪ { } = { ‹STRASSE›, ‹U› }。
文字列準同型 文字 列準同型（ 形式言語理論 では単に準 同型 と呼ばれることが多い ）とは、各文字を単一の文字列に置き換える文字列置換である。つまり、 各 文字 に対して、 （ は文字列）となる 。 [注 2] [4] f ( a ) = s {\displaystyle f(a)=s} s {\displaystyle s} a {\displaystyle a}
文字列準同型は、 自由モノイド 上の モノイド射 であり、空文字列と 文字列連結 の 二項演算 を 保存します。言語 が与えられた場合 、集合は の準 同型像 と呼ばれます 。 文字列の 逆準同型像は 次のように定義されます。 L {\displaystyle L} f ( L ) {\displaystyle f(L)} L {\displaystyle L} s {\displaystyle s}
f − 1 ( s ) = { w ∣ f ( w ) = s } {\displaystyle f^{-1}(s)=\{w\mid f(w)=s\}}
言語の逆準同型像 は次のように定義される。 L {\displaystyle L}
f − 1 ( L ) = { s ∣ f ( s ) ∈ L } {\displaystyle f^{-1}(L)=\{s\mid f(s)\in L\}}
一般的 に、 f ( f − 1 ( L ) ) ≠ L {\displaystyle f(f^{-1}(L))\neq L}
f ( f − 1 ( L ) ) ⊆ L {\displaystyle f(f^{-1}(L))\subseteq L}
そして
L ⊆ f − 1 ( f ( L ) ) {\displaystyle L\subseteq f^{-1}(f(L))}
あらゆる言語に対応 。 L {\displaystyle L}
正規言語のクラスは準同型と逆準同型に関して閉じている。 [5]
同様に、文脈自由言語は準同型 [注 3] と逆準同型に関して閉じている。 [6]
文字列準同型は、アルファベット の すべての a に対して となるとき、ε-フリー（または e-フリー）であるといわれます 。単純な一文字 置換暗号は、 （ε-フリー）文字列準同型の例です。 f ( a ) ≠ ε {\displaystyle f(a)\neq \varepsilon } Σ {\displaystyle \Sigma }
文字列準同型写像の例 g ucは 、上記の置換と同様に定義することで得られる。g uc (‹a›) = ‹A›, ..., g uc (‹0›) = εであるが、句読点文字については g uc を 未定義とする。逆準同型写像の例は以下の通りである。
g uc −1 ({‹SSS›}) = {‹sss›, ‹sß›, ‹ßs›} であり、 g uc (‹sss›) = g uc (‹sß›) = g uc (‹ßs›) = ‹SSS› であり、 g uc −1 ({ ‹A›, ‹bb› }) = { ‹a› }, g uc (‹a›) = ‹A› であるため、 g uc では ‹bb› に到達できません 。 後者の言語では、 g uc ( g uc −1 ({ ‹A›, ‹bb› })) = g uc ({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› } となる。準同型写像 g uc は 、例えば ‹0› を ε に写像するため、ε-free ではない。
各文字を 1 つの文字にマッピングする非常に単純な文字列準同型性の例として、 EBCDICでエンコードされた文字列を ASCII に変換することが挙げられます 。
文字列投影 s が文字列で が アルファベットの 場合、 の 文字列射影は に含まれないすべての文字を削除することによって得られる文字列です 。これは と書きます。これは 、 右側から文字を削除することによって正式に定義されます。 Σ {\displaystyle \Sigma } Σ {\displaystyle \Sigma } π Σ ( s ) {\displaystyle \pi _{\Sigma }(s)\,}
π Σ ( s ) = { ε if s = ε the empty string π Σ ( t ) if s = t a and a ∉ Σ π Σ ( t ) a if s = t a and a ∈ Σ {\displaystyle \pi _{\Sigma }(s)={\begin{cases}\varepsilon &{\mbox{if }}s=\varepsilon {\mbox{ the empty string}}\\\pi _{\Sigma }(t)&{\mbox{if }}s=ta{\mbox{ and }}a\notin \Sigma \\\pi _{\Sigma }(t)a&{\mbox{if }}s=ta{\mbox{ and }}a\in \Sigma \end{cases}}} ここで は 空文字列 を表します。文字列の射影は 、リレーショナル代数における射影 と本質的に同じです 。 ε {\displaystyle \varepsilon }
文字列射影は言語の射影 に昇格することができる 。 形式言語 L が与えられたとき、その射影は次のように与えられる。
π Σ ( L ) = { π Σ ( s ) | s ∈ L } {\displaystyle \pi _{\Sigma }(L)=\{\pi _{\Sigma }(s)\ \vert \ s\in L\}} [ 要引用 ]
右商と左商 文字列 s の文字 a の右 商 は、文字列 s の文字 a を右側から切り捨てたものです。これは と表記されます。文字列の 右側に a がない場合、結果は空文字列になります。つまり、 s / a {\displaystyle s/a}
( s a ) / b = { s if a = b ε if a ≠ b {\displaystyle (sa)/b={\begin{cases}s&{\mbox{if }}a=b\\\varepsilon &{\mbox{if }}a\neq b\end{cases}}} 空の文字列の商は次のように取得できます。
ε / a = ε {\displaystyle \varepsilon /a=\varepsilon } 同様に、モノイドの 部分集合が与えられたとき 、商部分集合を次のように定義できる。 S ⊂ M {\displaystyle S\subset M} M {\displaystyle M}
S / a = { s ∈ M | s a ∈ S } {\displaystyle S/a=\{s\in M\ \vert \ sa\in S\}} 左商も 同様に定義でき、演算は文字列の左側で行われます。 [ 引用が必要 ]
ホップクロフトとウルマン（1979）は、同じアルファベット上 の言語 L 1 と L 2 の商L 1 / L 2 をL 1 / L 2 = { s | ∃ t ∈ L 2 . st ∈ L 1 }と定義し て いる 。 [ 7 ] これ は 上記 の 定義 の 一般 化 で は ない 。 なぜなら 、 文字 列 s と 異なる 文字 a 、 b に対して 、 ホップクロフトとウルマンの定義は次を意味するからである。 { ε } ではなく {} になります。
単一言語L1 と 任意の言語 L2 の左商（ホップクロフトとウルマン1979と同様に定義される場合） は、 ブロゾフスキー微分 として知られている。L2 が 正規表現 で表される 場合、左商 も 同様に表される。 [8]
統語関係 モノイドの 部分集合の右商は、 S の 右 統語関係 と呼ばれる 同値関係 を定義する 。これは次のように与えられる。 S ⊂ M {\displaystyle S\subset M} M {\displaystyle M}
∼ S = { ( s , t ) ∈ M × M | S / s = S / t } {\displaystyle \sim _{S}\;\,=\,\{(s,t)\in M\times M\ \vert \ S/s=S/t\}} この関係は明らかに有限指数（同値類の数が有限）である。これは、族の右商が有限である場合に限る。つまり、
{ S / m | m ∈ M } {\displaystyle \{S/m\ \vert \ m\in M\}} は有限である。Mが 何らかのアルファベット上の単語のモノイドである 場合、 Sは 正規言語、すなわち 有限状態オートマトン によって認識可能な言語と なる。これについては、 統語的モノイド に関する記事でより詳細に議論されている 。 [ 要出典 ]
権利の取消 文字列 s から文字 a を右 消去すると は、文字列 s の右側から始めて、 文字 a が最初に出現する位置を削除することである。これは と表記され、再帰的に次のように定義される
。 s ÷ a {\displaystyle s\div a}
( s a ) ÷ b = { s if a = b ( s ÷ b ) a if a ≠ b {\displaystyle (sa)\div b={\begin{cases}s&{\mbox{if }}a=b\\(s\div b)a&{\mbox{if }}a\neq b\end{cases}}} 空の文字列は常にキャンセル可能です。
ε ÷ a = ε {\displaystyle \varepsilon \div a=\varepsilon } 明らかに、右のキャンセルと投影の 通勤 ：
π Σ ( s ) ÷ a = π Σ ( s ÷ a ) {\displaystyle \pi _{\Sigma }(s)\div a=\pi _{\Sigma }(s\div a)} [ 要引用 ]
接頭辞 文字列の接頭辞は 、 特定の言語に関して、文字列の
すべての 接頭辞 の集合です。
Pref L ( s ) = { t | s = t u for t , u ∈ Alph ( L ) ∗ } {\displaystyle \operatorname {Pref} _{L}(s)=\{t\ \vert \ s=tu{\mbox{ for }}t,u\in \operatorname {Alph} (L)^{*}\}} どこ 。 s ∈ L {\displaystyle s\in L}
言語の接頭辞 閉包 は
Pref ( L ) = ⋃ s ∈ L Pref L ( s ) = { t | s = t u ; s ∈ L ; t , u ∈ Alph ( L ) ∗ } {\displaystyle \operatorname {Pref} (L)=\bigcup _{s\in L}\operatorname {Pref} _{L}(s)=\left\{t\ \vert \ s=tu;s\in L;t,u\in \operatorname {Alph} (L)^{*}\right\}} 例： L = { a b c } then Pref ( L ) = { ε , a , a b , a b c } {\displaystyle L=\left\{abc\right\}{\mbox{ then }}\operatorname {Pref} (L)=\left\{\varepsilon ,a,ab,abc\right\}}
言語が 接頭辞閉じている と言われるのは、次の場合です 。 Pref ( L ) = L {\displaystyle \operatorname {Pref} (L)=L}
接頭閉包演算子は べき等で ある。
Pref ( Pref ( L ) ) = Pref ( L ) {\displaystyle \operatorname {Pref} (\operatorname {Pref} (L))=\operatorname {Pref} (L)} 接頭 辞関係は 、が成り立つ場合、かつその場合に 限って 成り立つ二項関係 である。この関係は、 接頭辞順序 の特定の例である 。 [ 要出典 ] ⊑ {\displaystyle \sqsubseteq } s ⊑ t {\displaystyle s\sqsubseteq t} s ∈ Pref L ( t ) {\displaystyle s\in \operatorname {Pref} _{L}(t)}
参照
注記 ^ すべての正規言語は文脈自由でもあるが、前者の定理は現在の定理によって暗示されるものではない。なぜなら前者は正規言語に対してより明確な結果をもたらすからである。 ^ 厳密に形式的には、準同型は 1 つの文字列だけからなる言語、つまり を生成します 。 f ( a ) = { s } {\displaystyle f(a)=\{s\}} ^ これは、任意の置換の下での前述の閉包から導かれる。
参考文献 ホップクロフト, ジョン・E.; ウルマン, ジェフリー・D. (1979). 『オートマトン理論、言語、計算入門 』 マサチューセッツ州レディング: アディソン・ウェスリー出版. ISBN 978-0-201-02988-8 . Zbl 0426.68001. （第3章を参照） ^ ホップクロフト、ウルマン（1979）、第3.2節、60ページ ^ ホップクロフト、ウルマン（1979）、第3.2節、定理3.4、p.60 ^ ホップクロフト、ウルマン（1979）、第6.2節、定理6.2、p.131 ^ ホップクロフト、ウルマン（1979）、Sect.3.2、p.60-61 ^ ホップクロフト、ウルマン（1979）、第3.2節、定理3.5、p.61 ^ ホップクロフト、ウルマン（1979）、第6.2節、定理6.3、p.132 ^ ホップクロフト、ウルマン（1979）、第3.2節、62ページ ^ ヤヌシュ・A・ブルゾゾフスキー (1964)。 「正規表現の派生」。 J ACM 。 11 (4): 481–494 . 土井 : 10.1145/321239.321249 。 S2CID 14126942。
