# 字符串运算

## 字符串的字母表

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

## 字符串代换

L 是一个语言，并设 ${\displaystyle \Sigma }$ 是它的字母表。字符串代换或简称代换是映射 f，它把 ${\displaystyle \Sigma }$ 中的字母映射到(可能有不同的字母表的)语言。比如，给定一个字母 ${\displaystyle a\in \Sigma }$，有 ${\displaystyle f(a)=L_{a}}$ 这里的 ${\displaystyle L_{a}\subset \Delta ^{*}}$ 是其字母表为 ${\displaystyle \Delta }$ 的某个语言。这个定义可被扩展到字符串为

${\displaystyle f(\varepsilon )=\varepsilon }$

${\displaystyle f(sa)=f(s)f(a)}$

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

## 字符串同态

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

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

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

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

## 字符串投影

${\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 \pi _{\Sigma }(L)=\{\pi _{\Sigma }(s)\vert s\in L\}}$

## 右商

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

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

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

## 语法关系

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

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

## 右取消

${\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 }}u\in L\}}$

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

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

## 引用

• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 3.)