コンピュータサイエンス の 形式言語理論 の分野では、さまざまな 文字列関数 が頻繁に使用されます。ただし、使用される表記法は コンピュータプログラミング で使用される表記法とは異なり 、理論領域でよく使用される関数の一部はプログラミングではほとんど使用されません。この記事では、これらの基本用語のいくつかを定義します。
文字列と言語 文字列は有限の文字の並びです。 空の文字列 は で表されます 。2 つの文字列 と の連結は で 表され 、短くすると になります 。空の文字列を連結しても違いはありません: 。文字列の連結は 結合的 です: 。
ε
{\displaystyle \epsilon }
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 ⋅ あなた ） = （ s ⋅ t ） ⋅ あなた
{\displaystyle s\cdot (t\cdot u)=(s\cdot t)\cdot u}
例えば、 。
（ ⟨ b ⟩ ⋅ ⟨ l ⟩ ） ⋅ （ ε ⋅ ⟨ 1つの h ⟩ ） = ⟨ b l ⟩ ⋅ ⟨ 1つの h ⟩ = ⟨ b l 1つの 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 )= L a となる。 ここで、 L a ⊆ Δ * はアルファベットが Δ である言語である。このマッピングは文字列に拡張できる。
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 (.) を大文字に変換することが挙げられます。これは次のように定義できます。
f uc を 文字列に拡張すると 、例えば次のようになる。
f uc (‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹STRASSE›}、 f uc (‹u2›) = {‹U›} ⋅ {ε} = {‹U›}であり、 f uc (‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}. fuc の 言語への拡張としては 、例えば
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 フリー) であると言われます 。単純な 1 文字 置換暗号は、 (ε フリー) 文字列準同型の例です。
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› であるのに対し、 ‹bb› には g uc では到達できないからである 。 後者の言語では、 g uc ( g uc −1 ({ ‹A›, ‹bb› })) = g uc ({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› } です。準同型写像 g uc は 、eg ‹0› を ε に写像するため、ε フリーではありません。
各文字を 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
に対して 、ホップクロフトとウルマンの定義は次を意味するからである。 { ε } ではなく {} になります。
単一言語 L 1 と任意の言語 L 2の左商（ホップクロフトとウルマン1979と同様に定義される場合）は、 ブロゾフスキー微分 として知られています。L 2 が 正規表現 で表される 場合 、左商も同様に表すことができます。 [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)。オートマトン理論 、 言語、計算入門 。マサチューセッツ州レディング: Addison-Wesley Publishing。ISBN 978-0-201-02988-8 .ZBL0426.68001 。 （第3章を参照）
^ ホップクロフト、ウルマン（1979）、セクション3.2、p.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、p.62 ^ ヤヌシュ・A・ブルゾゾフスキー (1964)。 「正規表現の派生」。 J ACM 。 11 (4): 481–494。 土井 : 10.1145/321239.321249 。 S2CID 14126942。
