字符串运算

在计算机科学中，在形式语言理论领域，经常使用各种字符串函数； 但是，所使用的符号与计算机编程所使用的符号不同，一些理论领域常用的函数在编程时很少使用。 本文定义了其中一些基本术语。

字符串是有限的字符序列。空字符串表示为 ε {\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} 。

语言是一组有限或无限的字符串。除了常见的集合运算，如并集、交集等，连接可以应用于语言：如果 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 } 通常被省略。

任意长度的所有十进制数的集合是无限语言的一个例子。

字符串的字母表是特定字符串中出现的所有字符的集合。 如果 s 是一个字符串，它的字母表示为

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

一种语言的字母表 S {\displaystyle S} 是出现在 S {\displaystyle S} 的任何字符串中的所有字符的集合

令 L 为一种语言，令 Σ 为其字母表。 字符串替换或简单的替换是一个映射 f，它将 Σ 中的字符映射到语言（可能在不同的字母表中）。 因此，例如，给定一个字符 a ∈ Σ，有 f(a)=La 其中 La ⊆ Δ* 是字母表为 Δ 的某种语言。 此映射可以扩展为字符串，如

f(ε)=ε

对于空字符串 ε，和

f(sa)=f(s)f(a)

对于字符串 s ∈ L 和字符 a ∈ Σ。 字符串替换可以扩展到整个语言，因为

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

常规语言在字符串替换下是封闭的。 也就是说，如果将一种正则语言的字母表中的每个字符替换为另一种正则语言，结果仍然是一种正则语言。类似地，上下文无关语言在字符串替换下是封闭的。