文字列操作

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

文字列は文字の有限列です。空文字列は で表されます。${\displaystyle \varepsilon }$2つの文字列の連結${\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}$。

例えば、${\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 \}}$3桁の10進数全体の集合は次のように得られます。${\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)}$。

例えば、セット${\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 )= L _aとなる。ここでL _a ⊆ Δ ^*はアルファベットが Δ である何らかの言語である。この写像は文字列にも拡張できる。

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を文字列に拡張する場合、例えば

• 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› }。

文字列準同型（形式言語理論では単に準同型と呼ばれることが多い）とは、各文字が単一の文字列に置き換えられるような文字列置換のことである。つまり、${\displaystyle f(a)=s}$、 どこ${\displaystyle s}$各文字は文字列です${\displaystyle a}$[^{注2 ] [ 4 ]}

文字列準同型は、自由モノイド上のモノイド準同型であり、空文字列と文字列連結の二項演算を保存する。${\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 ]}

文字列準同型写像は、以下の条件を満たす場合にεフリー（またはeフリー）であると言われる。${\displaystyle f(a)\neq \varepsilon }$アルファベットのすべてのaについて${\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› であり、‹bb› は}g _ucによって到達できないからである。

後者の言語では、g _uc ( g _uc ⁻¹ ({ ‹A›, ‹bb› })) = g _uc ({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› } となります。準同型写像g _{uc は}eg ‹0› を ε に写像するため、ε フリーではありません。

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

sが文字列の場合、${\displaystyle \Sigma }$はアルファベットであり、sの文字列射影は、 に含まれないすべての文字を削除することによって得られる文字列です。${\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を切り捨てた値です。これは次のように表されます。${\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に対して、ホップ クロフトとウルマンの定義は、{ ε }ではなく{}を生成する。

単一言語L ₁と任意の言語L ₂の左商 (Hopcroft と Ullman 1979 と同様に定義される場合) は、 Brzozowski 微分として知られています。L _{2 が}正規表現で表されている場合、左商も正規表現で表すことができます。^{[ 8 ]}

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

${\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)}$この関係は、接頭辞順序の具体的な例です。

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

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