在计算机科学领域形式语言理论中,经常用到各种字符串函数;但是符号不同于计算机编程中所用到的,某些在理论领域中常用的函数,在编程中很少用到。本文定义其中一些基本术语。
字符串的字母表是在一个特定字符串中出现的所有字母的列表。如果 s 是字符串,则它的字母表指示为
![{\displaystyle \operatorname {Alph} (s)}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/fd51e04e6bd1ffe7fb1a810455fc1ac4f8f213d9)
这可以等价地认为是先把字符串中的所有字母按照给定的顺序排好,再去掉其中重复者。
设 L 是一个语言,并设
是它的字母表。字符串代换或简称代换是映射 f,它把
中的字母映射到(可能有不同的字母表的)语言。比如,给定一个字母
,有
这里的
是其字母表为
的某个语言。这个定义可被扩展到字符串为
![{\displaystyle f(\varepsilon )=\varepsilon }](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/a85a87b97af647c7e9e54d19706623b76973bbbf)
对于空串
,和
![{\displaystyle f(sa)=f(s)f(a)}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/2a3149bf49ef29f18af4d96f71dd64a888cd87b9)
对于字符串
。字符串代换可以被扩展到整个语言为
![{\displaystyle f(L)=\bigcup _{s\in L}f(s)}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/1511863693744491845b202491475c9d126c7cd4)
字符串代换的一个例子出现在正则语言中,它闭合于字符串代换之下。就是说,如果一个正规语言的字母被另一个正规语言所代换,结果仍是正规语言。
字符串同态是使得每个字母被替代为一个单一字符串的字符串代换。就是说,
,这里的 s 是字符串,对于每个字母 a。字符串同态是保持字符串连接二元运算的同态。给定一个语言 L,
的集合叫做 L 的同态像。字符串 s 的逆同态像被定义为
![{\displaystyle f^{-1}(s)=\{w\vert f(w)=s\}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/0b79c56fd6e76e5152e66d9c12ed3c240b4e340f)
而语言 L 的逆同态像被定义为
![{\displaystyle f^{-1}(L)=\{s\vert f(s)\in L\}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/d3dfae5d6615de2ca6dd6a6a23c9822008293103)
注意一般的说
,然而确实有
![{\displaystyle f(f^{-1}(L))\subseteq L}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/9fe260491a8b84800bb878d272ceb2299e311b47)
和
![{\displaystyle L\subseteq f^{-1}(f(L))}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/7734c5ef5b1cfd35f4efb356d201cd5aa5a9cc1b)
对于任何语言 L。简单单一字母置换密码是字符串代换的例子。
如果 s 是字符串,而
是字母表,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}}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/e4d1f7483201880d7159334d79826cd9abe6c4a4)
这里的
指示空串。字符串的投影本质上同于关系代数中的投影。
字符串投影可以提升为语言的投影。给定形式语言 L,它的投影给出自
![{\displaystyle \pi _{\Sigma }(L)=\{\pi _{\Sigma }(s)\vert s\in L\}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/df759b920cf34b3062ef0618dab9cdadf6c33611)
字符串 s 与字母 a 的右商是在字符串 s 中切断右手端字母 a 得到的字符串。它被指示为
。如果字符串在右手端没有 a,则结果是空串。就是:
![{\displaystyle (sa)/b={\begin{cases}s&{\mbox{if }}a=b\\\varepsilon &{\mbox{if }}a\neq b\end{cases}}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/3e3e09a4d499f91636b41ece953e2d950a6107f4)
空串的右商可以是:
![{\displaystyle \varepsilon /a=\varepsilon }](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/b6aa5cd66d00435b0f1de7761599ae278d9d2433)
类似的,给出幺半群
的子集
,可以定义商子集为
![{\displaystyle S/a=\{s\in M\vert sa\in S\}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/c9ef9a0aed42d43893619aeb9bdf7af87397e45b)
左商可以类似的定义,运算发生在字符串的左端。
幺半群
的子集
的右商定义了一个等价关系,叫做 S 的右语法关系。它给出为
![{\displaystyle \sim _{S}\;\,=\,\{(s,t)\in M\times M\vert S/s=S/t\}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/c97fad3d9e524ba4c074aaf7973571b977225aba)
关系明显是有有限索引的(有有限数目个等价类),当且仅当右商族有限的;就是说如果
![{\displaystyle \{S/m\vert m\in M\}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/3a21ec330c0b0c7fb8718ead9cf5c5269c494db8)
是有限的。在这种情况下,S 是可识别语言,就是说可被有限状态自动机识别的语言。这个在语法幺半群中详细讨论。
字符串 s 与字母 a 的右取消是切除字符串 s 右手端的字母 a 的首次出现得到的字符串。它被指示为
并被递归的定义为
![{\displaystyle (sa)\div b={\begin{cases}s&{\mbox{if }}a=b\\(s\div b)a&{\mbox{if }}a\neq b\end{cases}}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/c26c8a254adb20525c0d4fc9c9f7462327614904)
空串总是可取消的:
![{\displaystyle \varepsilon \div a=\varepsilon }](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/b1a9818e928f73eea2b21d313f4b1f01c71540cc)
明显的,右取消和投影可交换:
![{\displaystyle \pi _{\Sigma }(s)\div a=\pi _{\Sigma }(s\div a)}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/e744017a7995878125e4b4580fa2ee9b74feaabd)
字符串的前缀是关于给定语言一个字符串的所有前缀的集合:
![{\displaystyle \operatorname {Pref} _{L}(s)=\{t\vert s=tu{\mbox{ for }}u\in L\}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/1b6fdd5d2c712638eb183689165909df37b60f51)
语言的前缀闭包是
![{\displaystyle \operatorname {Pref} (L)=\bigcup _{s\in L}\operatorname {Pref} _{L}(s)}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/fad35a51acf4b5ccabdc06d9dc25d798271a6387)
一个语言叫做前缀闭合的,如果
。明显的,前缀闭包算子是幂等的:
![{\displaystyle \operatorname {Pref} (\operatorname {Pref} (L))=\operatorname {Pref} (L)}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/e08d8ee94c1daa430a4f88f8ab4786e7da5c06a1)
前缀关系是二元关系
,有着
当且仅当
。
前缀文法生成(关于这个文法)前缀闭合的语言。
- 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.)