文字列操作

Operations in formal language theory

コンピュータサイエンスの形式言語理論の分野では、様々な文字列関数が頻繁に用いられます。しかし、その表記法はコンピュータプログラミングで使用される表記法とは異なり、理論分野でよく用いられる関数の中には、プログラミングではほとんど用いられないものもあります。この記事では、これらの基本用語のいくつかを定義します。

文字列と言語

文字列は有限の文字の並びです。空文字列は で表されます。2つの文字列との連結はで表され、短く で表されます。空文字列との連結には違いはありません。文字列の連結は結合的です ${\displaystyle \varepsilon }$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s\cdot t}$ ${\displaystyle st}$ ${\displaystyle s\cdot \varepsilon =s=\varepsilon \cdot s}$ ${\displaystyle s\cdot (t\cdot u)=(s\cdot t)\cdot u}$

例えば、。 ${\displaystyle (\langle b\rangle \cdot \langle l\rangle )\cdot (\varepsilon \cdot \langle ah\rangle )=\langle bl\rangle \cdot \langle ah\rangle =\langle blah\rangle }$

言語とは、有限または無限の文字列の集合です。和集合、積集合などの通常の集合演算に加えて、言語には連結を適用できます。とが両方とも言語である場合、それらの連結は、 の任意の文字列と の任意の文字列の連結の集合として定義され、正式にはとなります。ここでも、連結ドットは簡潔にするために省略されることがよくあります。 ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S\cdot T}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S\cdot T=\{s\cdot t\mid s\in S\land t\in T\}}$ ${\displaystyle \cdot }$

空文字列のみからなる言語は、空言語 と区別する必要があります。前者を任意の言語に連結しても変化はありません: ですが、後者を連結すると常に空言語 が生成されます: 。言語の連結は結合的です: 。 ${\displaystyle \{\varepsilon \}}$ ${\displaystyle \{\}}$ ${\displaystyle S\cdot \{\varepsilon \}=S=\{\varepsilon \}\cdot S}$ ${\displaystyle S\cdot \{\}=\{\}=\{\}\cdot S}$ ${\displaystyle S\cdot (T\cdot U)=(S\cdot T)\cdot U}$

例えば、 を省略すると、3桁の10進数全体の集合は となります。任意の長さの10進数全体の集合は、無限言語の一例です。 ${\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 \}}$ ${\displaystyle D\cdot D\cdot D}$

文字列のアルファベット

文字列のアルファベットとは、特定の文字列に現れるすべての文字の集合である。sが文字列である場合、そのアルファベットは次のように表される。

${\displaystyle \operatorname {Alph} (s)}$

言語のアルファベット は、 の任意の文字列に出現するすべての文字の集合であり、正式には です。 ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle \operatorname {Alph} (S)=\bigcup _{s\in S}\operatorname {Alph} (s)}$

たとえば、セットは文字列 のアルファベットであり、上記は上記の言語のアルファベットであるだけでなく、すべての 10 進数の言語のアルファベットでもあります。 ${\displaystyle \{\langle a\rangle ,\langle c\rangle ,\langle o\rangle \}}$ ${\displaystyle \langle cacao\rangle }$ ${\displaystyle 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]

${\displaystyle f(L)=\bigcup _{s\in L}f(s)}$

正規言語は文字列置換に対して閉じている。つまり、正規言語のアルファベットの各文字を別の正規言語に置き換えても、結果は依然として正規言語である。^[2]同様に、文脈自由言語は文字列置換に対して閉じている。^{[3] [注 1]}

簡単な例としては、f _uc (.) を大文字に変換することが挙げられます。これは次のように定義できます。

文字	言語にマッピング	備考
×	f 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]} ${\displaystyle f(a)=s}$ ${\displaystyle s}$ ${\displaystyle a}$

文字列準同型は、自由モノイド上のモノイド射であり、空文字列と文字列連結の二項演算 を保存します。言語 が与えられた場合、集合はの準同型像と呼ばれます。文字列の逆準同型像は次のように定義されます。 ${\displaystyle L}$ ${\displaystyle f(L)}$ ${\displaystyle L}$ ${\displaystyle s}$

${\displaystyle f^{-1}(s)=\{w\mid f(w)=s\}}$

言語の逆準同型像は次のように定義される。 ${\displaystyle L}$

${\displaystyle f^{-1}(L)=\{s\mid f(s)\in L\}}$

一般的に、 ${\displaystyle f(f^{-1}(L))\neq L}$

${\displaystyle f(f^{-1}(L))\subseteq L}$

そして

${\displaystyle L\subseteq f^{-1}(f(L))}$

任意の言語に対して。 ${\displaystyle L}$

正規言語のクラスは準同型と逆準同型に関して閉じている。^[5] 同様に、文脈自由言語は準同型^[注3]と逆準同型に関して閉じている。^[6]

文字列準同型は、アルファベット のすべてのaに対して となるとき、ε-フリー（または e-フリー）であるといわれます。単純な一文字置換暗号は、（ε-フリー）文字列準同型の例です。 ${\displaystyle f(a)\neq \varepsilon }$ ${\displaystyle \Sigma }$

文字列準同型写像の例g _ucは、上記の置換と同様に定義することで得られる。g _uc (‹a›) = ‹A›, ..., g _uc (‹0›) = εであるが、句読点文字についてはg _ucを未定義とする。逆準同型写像の例は以下の通りである。

• g _uc ⁻¹ ({‹SSS›}) = {‹sss›, ‹sß›, ‹ßs›} であり、g _uc (‹sss›) = g _uc (‹sß›) = g _uc (‹ßs›) = ‹SSS› であり、
• g _uc ⁻¹ ({ ‹A›, ‹bb› }) = { ‹a› }, g _{uc (‹a›) = ‹A› であるため、} g _ucでは ‹bb› に到達できません。

後者の言語では、g _uc ( g _uc ⁻¹ ({ ‹A›, ‹bb› })) = g _uc ({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› } となる。準同型写像g _{uc は}、例えば ‹0› を ε に写像するため、ε-free ではない。

各文字を 1 つの文字にマッピングする非常に単純な文字列準同型性の例として、EBCDICでエンコードされた文字列をASCIIに変換することが挙げられます。

文字列射影

sが文字列で、がアルファベットの場合、sの文字列射影は、 に含まれないすべての文字を削除することによって得られる文字列です。これは と書きます。これは、右側から文字を削除することによって正式に定義されます ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle \pi _{\Sigma }(s)\,}$

${\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が与えられたとき、その射影は次のように与えられる。

${\displaystyle \pi _{\Sigma }(L)=\{\pi _{\Sigma }(s)\ \vert \ s\in L\}}$^[要引用]

右商と左商

文字列sの文字aの右商は、文字列sの文字aを右側から切り捨てたものです。これは と表記されます。文字列の右側にaがない場合、結果は空文字列になります。つまり、 ${\displaystyle s/a}$

${\displaystyle (sa)/b={\begin{cases}s&{\mbox{if }}a=b\\\varepsilon &{\mbox{if }}a\neq b\end{cases}}}$

空の文字列の商は次のように取得できます。

${\displaystyle \varepsilon /a=\varepsilon }$

同様に、モノイドの部分集合が与えられたとき、商部分集合を次のように定義できる。 ${\displaystyle S\subset M}$ ${\displaystyle M}$

${\displaystyle S/a=\{s\in M\ \vert \ sa\in S\}}$

左商も同様に定義でき、演算は文字列の左側で行われます。^{[引用が必要]}

ホップクロフトとウルマン（1979）は、同じアルファベット上の言語L ₁とL ₂の商L 1 / L 2 をL 1 / L 2 = { s | ∃ t ∈ L 2 . st ∈ L 1 }と定義して_いる。[ ₇ ]_これは上記_の定義の一般化では_ない。なぜなら、文字_列sと^異なる文字a 、 bに対して、ホップクロフトとウルマンの定義は次を意味するからである。{ ε } ではなく {} になります。

単一言語L1_と任意の言語L2の左商（ホップクロフトとウルマン1979と同様に定義される場合）_は、ブロゾフスキー微分として知られている。L2が正規表現で表される場合、左商_も同様に表される。^[8]

統語的関係

モノイドの部分集合の右商は、 Sの右統語的関係と呼ばれる同値関係を定義します。これは次のように与えられます ${\displaystyle S\subset M}$ ${\displaystyle M}$

${\displaystyle \sim _{S}\;\,=\,\{(s,t)\in M\times M\ \vert \ S/s=S/t\}}$

この関係は明らかに有限指数（同値類の数が有限）である。これは、族の右商が有限である場合に限る。つまり、

${\displaystyle \{S/m\ \vert \ m\in M\}}$

は有限である。Mが何らかのアルファベット上の単語のモノイドである場合、 Sは正規言語、すなわち有限状態オートマトンによって認識可能な言語となる。これについては、統語的モノイドに関する記事でより詳細に議論されている。^[要出典]

右打ち消し

文字列sから文字a を削除する右打ち消しとは、文字列sの右側から始めて、最初に出現する文字aを削除することです。これは と表記され、再帰的に次のように定義されます ${\displaystyle s\div a}$

${\displaystyle (sa)\div b={\begin{cases}s&{\mbox{if }}a=b\\(s\div b)a&{\mbox{if }}a\neq b\end{cases}}}$

空の文字列は常にキャンセル可能です。

${\displaystyle \varepsilon \div a=\varepsilon }$

明らかに、右のキャンセルと投影の通勤：

${\displaystyle \pi _{\Sigma }(s)\div a=\pi _{\Sigma }(s\div a)}$^[要引用]

接頭辞

文字列の接頭辞とは、特定の言語における文字列の すべての接頭辞の集合です

${\displaystyle \operatorname {Pref} _{L}(s)=\{t\ \vert \ s=tu{\mbox{ for }}t,u\in \operatorname {Alph} (L)^{*}\}}$

どこ。 ${\displaystyle s\in 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\}}$

例：
${\displaystyle L=\left\{abc\right\}{\mbox{ then }}\operatorname {Pref} (L)=\left\{\varepsilon ,a,ab,abc\right\}}$

言語が接頭辞閉じていると言われるのは、次の場合です。 ${\displaystyle \operatorname {Pref} (L)=L}$

接頭閉包演算子はべき等である。

${\displaystyle \operatorname {Pref} (\operatorname {Pref} (L))=\operatorname {Pref} (L)}$

接頭辞関係は、が成り立つ場合、かつその場合に限って成り立つ二項関係 である。この関係は、接頭辞順序の特定の例である。^[要出典] ${\displaystyle \sqsubseteq }$ ${\displaystyle s\sqsubseteq t}$ ${\displaystyle s\in \operatorname {Pref} _{L}(t)}$

参照

• プログラミング言語の比較（文字列関数）
• リーバイの補題
• 文字列（コンピュータサイエンス） —文字列に対するより基本的な演算の定義と実装

注釈

1. すべての正規言語は文脈自由ですが、前の定理は現在の定理から導き出されるわけではありません。なぜなら、前者は正規言語に対してより明確な結果をもたらすからです
2. 厳密に形式的には、準同型は 1 つの文字列だけからなる言語、つまり を生成します。 ${\displaystyle f(a)=\{s\}}$
3. これは、任意の置換の下での前述の閉包から導かれる。

参考文献

• ホップクロフト、ジョン・E.、ウルマン、ジェフリー・D. (1979). 『オートマトン理論、言語、計算入門』マサチューセッツ州レディング：アディソン・ウェスリー出版. ISBN 978-0-201-02988-8. Zbl  0426.68001. （第3章を参照）

1. ホップクロフト、ウルマン（1979）、第3.2節、60ページ
2. ホップクロフト、ウルマン（1979）、第3.2節、定理3.4、p.60
3. ホップクロフト、ウルマン（1979）、第6.2節、定理6.2、p.131
4. ホップクロフト、ウルマン（1979）、Sect.3.2、p.60-61
5. ホップクロフト、ウルマン（1979）、第3.2節、定理3.5、p.61
6. ホップクロフト、ウルマン（1979）、第6.2節、定理6.3、p.132
7. ホップクロフト、ウルマン（1979）、第3.2節、62ページ
8. ヤヌシュ・A・ブルゾゾフスキー(1964)。 「正規表現の派生」。J ACM。11 (4): 481–494 .土井: 10.1145/321239.321249。S2CID  14126942。

Retrieved from "https://en.wikipedia.org/w/index.php?title=String_operations&oldid=1323586938"