字符串运算

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

字符串的字母表是在一个特定字符串中出现的所有字母的列表。如果 是字符串，则它的字母表指示为

这可以等价地认为是先把字符串中的所有字母按照给定的顺序排好，再去掉其中重复者。

设 是一个语言，并设 ${\displaystyle \mathrm{\Sigma <!--\; \Sigma \; -->}}$，它把 ${\displaystyle \mathrm{\Sigma <!--\; \Sigma \; -->}}$ 是字符串，对于每个字母 。字符串同态是保持字符串连接二元运算的同态。给定一个语言 ，${\displaystyle f(L)}$ 的同态像。字符串 的逆同态像被定义为

而语言 的逆同态像被定义为

注意一般的说 ${\displaystyle f(f^{-<!--\; -\; -->1}(L))\ne <!--\; \ne \; -->L}$。简单单一字母置换密码是字符串代换的例子。

如果 是字符串，而 ${\displaystyle \mathrm{\Sigma <!--\; \Sigma \; -->}}$ 的字符串投影是通过删除不在 ${\displaystyle \mathrm{\Sigma <!--\; \Sigma \; -->}}$，它的投影给出自

字符串 与字母 的右商是在字符串 中切断右手端字母 得到的字符串。它被指示为 ${\displaystyle s/a}$，则结果是空串。就是:

空串的右商可以是:

类似的，给出幺半群 ${\displaystyle M}$ 的右语法关系。它给出为

关系明显是有有限索引的(有有限数目个等价类)，当且仅当右商族有限的；就是说如果

是有限的。在这种情况下， 是可识别语言，就是说可被有限状态自动机识别的语言。这个在语法幺半群中详细讨论。

字符串 与字母 的右取消是切除字符串 右手端的字母 的首次出现得到的字符串。它被指示为 ${\displaystyle s÷<!--\; ÷\; -->a}$ 并被递归的定义为

空串总是可取消的:

明显的，右取消和投影可交换:

字符串的前缀是关于给定语言一个字符串的所有前缀的集合:

语言的前缀闭包是

一个语言叫做前缀闭合的，如果 ${\displaystyle \mathrm{Pref}<!--\; \; -->(L)=L}$。明显的，前缀闭包算子是幂等的:

前缀关系是二元关系 ${\displaystyle ⊑<!--\; ⊑\; -->}$，有着 ${\displaystyle s⊑<!--\; ⊑\; -->t}$ 当且仅当 ${\displaystyle s\in <!--\; \in \; -->{\mathrm{Pref}}_L<!--\; \; -->(t)}$。

前缀文法生成(关于这个文法)前缀闭合的语言。