字符串运算

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

字符串的字母表

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

 

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

字符串代换

L 是一个语言,并设   是它的字母表。字符串代换或简称代换是映射 f,它把   中的字母映射到(可能有不同的字母表的)语言。比如,给定一个字母  ,有   这里的   是其字母表为   的某个语言。这个定义可被扩展到字符串为

 

对于空串  ,和

 

对于字符串  。字符串代换可以被扩展到整个语言为

 

字符串代换的一个例子出现在正则语言中,它闭合于字符串代换之下。就是说,如果一个正则语言的字母被另一个正则语言所代换,结果仍是正则语言。

字符串同态

字符串同态是使得每个字母被替代为一个单一字符串的字符串代换。就是说, ,这里的 s 是字符串,对于每个字母 a。字符串同态是保持字符串连接二元运算同态。给定一个语言 L  的集合叫做 L同态像。字符串 s逆同态像被定义为

 

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

 

注意一般的说  ,然而确实有

 

 

对于任何语言 L。简单单一字母置换密码是字符串代换的例子。

字符串投影

如果 s 是字符串,而   是字母表,s字符串投影是通过删除不在   中的所有字母结果的字符串。它被写为  。它通过从右手端切除字母来得出形式定义:

 

这里的   指示空串。字符串的投影本质上同于关系代数中的投影。

字符串投影可以提升为语言的投影。给定形式语言 L,它的投影给出自

 

右商

字符串 s 与字母 a右商是在字符串 s 中切断右手端字母 a 得到的字符串。它被指示为  。如果字符串在右手端没有 a,则结果是空串。就是:

 

空串的右商可以是:

 

类似的,给出幺半群   的子集  ,可以定义商子集为

 

左商可以类似的定义,运算发生在字符串的左端。

语法关系

幺半群   的子集   的右商定义了一个等价关系,叫做 S语法关系。它给出为

 

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

 

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

右取消

字符串 s 与字母 a右取消是切除字符串 s 右手端的字母 a 的首次出现得到的字符串。它被指示为   并被递归的定义为

 

空串总是可取消的:

 

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

 

前缀

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

 

语言的前缀闭包

 

一个语言叫做前缀闭合的,如果  。明显的,前缀闭包算子是幂等的:

 

前缀关系二元关系  ,有着   当且仅当  

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

参见

引用

  • 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.)