字符串操作

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

字符串是一个有限的字符序列。空的字符串表示为一个语言是一个有限或无限的字符串集。除了通常的集合操作，如联合，相交等，连接可以应用于语言：如果两个{displaystyleT}都是语言，那么它们的连接可以应用于语言。是语言，它们的连接方式是.所有任意长度的十进制数的集合是一个无限语言的例子。字符串的字母表字符串的字母表是一个特定字符串中出现的所有字符的集合。如果s是一个字符串，它的字母表被表示为{displaystyleS}是一个语言S的字母表。的任何字符串中出现的所有字符的集合。S{displaystyleS}的任何字符串中出现的所有字符的集合，形式为：{displaystyleS}。，从形式上看。{displaystyleDcdotDcdotD}以及所有十进制数的语言。以及所有十进制数字的语言。字符串置换让L是一种语言，让Σ是其字母表。字符串置换或简称置换是一种映射f，它将Σ中的字符映射到语言（可能是不同的字母表）。因此，例如，给定一个字符a∈Σ，就有f(a)=La，其中La⊆Δ*是某种语言，其字母表是Δ。

正则语言在字符串替换下是封闭的。也就是说，如果一个正则语言的字母表中的每个字符都被另一个正则语言所替代，那么结果仍然是一个正则语言。类似地，无语境语言在字符串替代下是封闭的。一个简单的例子是fuc(.)到大写字母的转换，它可以被定义如下。