第2章 语言与字符串这个理论中，我们要把问题交为更具体的问题，“给定字符串s 和语言L ，s 是否在L 中？”进行形式化之前，要先定义几个术语。

字母表（alphabet ）记为∑，是个有限集。

∑的成员称为符号（symbols ）或字符（characters ）。

2.1 字符串字符串（string ）是某个字母表∑中符号的有限序列。

给定字母表∑，可以从∑构造的最短字符串是空串，记为ε。

字母表∑中的所有字符串集合记为∑*。

这里采用Kleene 星号运算符，定义如例2.1所示。

例2.1 字母表字母表名称字母表符号 例子字符串 英语字母表{a, b, c, …, z} ε, aabbcg, aaaaa 二进制字母表{0, 1} ε, 0, 001100 星号字母表音乐字母表 {}教材中直接数符号和字符串写成like this 。

2.1.1 字符串函数字符串s 的长度（length ）记为|s |，是s 中的字符个数。

例如：|ε| = 0|1001101| = 7对任意符号c 和字符串s ，函数#c (s )定义为s 中符号c 出现的次数，例如#a (abbaaa)=4。

接合（concatenation ）字符串s 与t 写成s ||t 或st ，就是在s 后面添加t 。

例如，如果x = good ，y = bye ，则xy = goodbye 。

因此|xy | = |x | + |y |。

空串ε在接合字符串时，字符串不变，因此∀x (x ε = εx = x )。

接合作为字符串函数是结合性的，因此∀s ，t ，w ((st )w = s (tw ))。

下面定义字符串复制（replication ）。

对每个字符串w 和自然数i ，w i 定义为w 0 = εw i +1 = w i w在8第2章语言与字符串例如：a3 = aaa(bye)2 = byebyea0b3 = bbb最后，我们定义字符串的逆（reversal）。

对每个字符串w，字符串的逆写成W R，定义为如果|w| = 0，则W R = w = ε。

如果|w|≥1，则∃a∈∑ (∃u∈∑* (w = ua))，（即w最后一个字符为a。

）然后定义W R=au R。

定理2.1 字符串的接合与逆定理：如果w与x为字符串，则(wx)R=x R w R。

例如，(nametag)R = (tag)R(name)R = gateman。

证明：我们对|x|进行了归纳：基本case:|x| = 0。

则x=ε，(wx)R = (wε)R= (w)R = εw R=εR w R=x R w R。

证明：∀n≥0 (((|x| = n)→ ((wx)R= x R w R))→((|x| = n+1) →((wx)R = x R w R)))。

对任意字符串x，其中|x| = n+1，则x=ua，其中a为字符，|u|=n。

因此：(wx)R = (w(ua))R将x写成ua= ((wu)a)R接合的结合律= a(wu) R逆的定义= a(u R w R) 归纳假设=（au）R w R接合的结合律=（ua）R w R逆的定义=x R w R将ua写成x2.1.2 字符串的关系字符串s为t的子串（substring）的充分必要条件为s在t中连续出现。

例如：aaa是 aaabbbaaa的子串aaaaaa不是 aaabbbaaa的子串字符串s为t的正子串（proper substring）的充分必要条件为s是t的子串，且s≠t。

每个字符串是自己的子串，但不是其正子串。

空串ε是任何字符串的子串。

字符串s是t的前缀（prefix）的充分必要条件为∃x∈∑*(t = sx)。

字符串s是t的正前缀（proper prefix）的充分必要条件为s是t的前缀，且s≠t。

每个字符串是自己的前缀，但不是其正前缀。

空串ε是任何字符串的前缀。

例如，abba的前缀为ε，a，ab，abb，abba。

字符串s是t的后缀（suffix）的充分必要条件为∃x∈∑* (t = xs）。

字符串s是t的正后缀（proper suffix）的充分必要条件为s是t的后缀，且s≠t。

每个字符串是自己的后缀，但不是其正后缀。

空串ε是任何字符串的后缀。

例如，abba的后缀为ε，a，ab，abb，abba。

2.2 语言 92.2 语言语言（language）是有限字母表∑上的（有限或无限）字符串集。

介绍多种语言时，可以用∑L表示语言L的字符串采用哪个字母表。

例2.2给定字母表定义语言设∑ = {a，b}. ∑* = {ε，a，b，aa，ab，ba，bb，aaa，aab，...}.∑上的语言例子包括：Ø，{ε}，{a，b}，{ε，a，aa，aaa，aaaa，aaaaa}，{ε，a，aa，aaa，aaaa，aaaaa，...}2.2.1 定义语言的方法我们用各种方法定义语言。

由于语言是集合，因此可以用任何时候集合定义方法定义。

例如，可以指定特征函数，即对集合中每个元素为真而对其他元素为假的谓词。

例2.3所有a在所有b之前设L={w{a∈，b}*:，w中所有a在所有b之前}，则字符串ε，a，aa，aaa，aabbb和bb属于L，而aba，ba与abc不属于L。

注意有些字符串平凡满足L成员的要求。

规则没有要求其中有a或b，只是说所有a在所有b之前（如果有）。

如果没有a或没有b，则不会违反这个规则，因此字符串ε，a，aa与bb平凡满足L成员的要求。

例2.4字符串以a结尾∈，b}*(x =ya)}，则字符串a，aa，aaa，bbaa与ba属于L，而ε，bab 设L={x: ∃y{a与bca不属于L。

L中的所有字符串可以表示为{a，b}*中的字符串接合一个a到末尾。

例2.5用英语描述语言的问题∈ 1, 2, 3, 4, 5, 6, 7, 8, 9}*，且x、y看成自然数的十进制表示时，设L={x#y:x，y{0,square(x)=y}。

字符串3#9和12#144属于L，而3#18、12与12#12#12不属于L。

字符串#?是不是属于L？取决于怎么理解“x、y看成自然数的十进制表示”。

ε是不是某个自然数的十进制表示？将字符串变成数字的算法可能将ε换算为0，则0是0的平方，因此#属于L。

反过来，如果将字符串变成数字的算法认为ε是无效输入，则#不属于L。

这个例子说明存在用英语描述语言的问题，即歧义性。

我们只能使用无歧义的术语，下面将介绍其他避免这个问题的定义方法。

例2.6空语言设L = {} = ∅，L是空语言，不包含任何字符串。

例2.7空语言不同于空串L = {ε}是包含空串ε的语言，不同于空语言。

10第2章语言与字符串上面介绍的所有例子符合语言的定义，即字符串集合，但不同于日常用法。

日常语言也符合这个定义。

例2.8英语不是定义合理的语言设L={w：w英语句子}例如：Kerry hit the ball. /*显然属于LColorless green ideas sleep furiously4. /*语法正确，但是什么意思呢The window needs fixed. /*L的方言Ball the Stacy hit blue. /*显然不属于L像英语之类语言的问题是没有明确规定包含什么字符串。

如果事先无法产生形式规范，就无法建立语言。

英语、中文、西班牙语之类的自然语言虽然很难指定，但非常重要。

因此，人们投入巨大精力创建形式和计算有效的描述，以便在文法检查、文本数据库抽取之类应用程序中运用。

在创建英语之类自然语言的形式描述时，可以使用我们开发的理论，见第2部分和第3部分。

例2.9停止问题语言∈ b}*:all a’s precede all b’s}设L = {w: w是对所有输入停止的C语言程序}。

L比{x{a,之类更复杂。

但和英语不同，它具有明确的形式规范。

我们要介绍的理论指出了L的许多重要特性。

可以用字符串定义的关系定义语言。

例2.10使用前缀关系我们用字符串定义的前缀关系定义如下语言：L1 ={w∈ {a，b}*: no prefix of w contains b}={ε，a，aa，aaa，aaaa，aaaaa，aaaaaa，...}L2 ={w∈ {a，b}*: no prefix of w starts with b}={w∈ {a，b}*: the first character of w is a }∪ {ε}L3 ={w∈ {a，b}*: every prefix of w starts with b}= ∅L3等于∅，因为ε是每个字符串的前缀。

由于ε不以b开头，因此没有一个字符串符合L3要求。

前面曾介绍过，我们定义了字符串的复制运算符：对任何时候字符串s和整数n，s n=n 的n个副本接合。

例如，(bye)2=byebye。

可以用复制定义语言而不是定义各个字符串，只要n用变量而不是特定常量。

例2.11用复制定义语言设L={a n:n≥0}，L={ε，a，aa，aaa，aaaa，aaaaa, ...}.2.2 语言 11语言是集合，因此如果要提供语言的计算定义，可以指定：y语言生成器，枚举这个语言的元素，或者，y语言识别器，确定某个字符串是否属于这个语言，是返回真值，不是返回假值。

例如，逻辑定义L={x:∃y{a∈，b}*(x=ya)}可以返回语言生成器（枚举器）或语言识别器。

考虑一个语言L的枚举器时，有时可能要考虑L生成元素的顺序。

如果∑L的元素是D 的顺序（例如写字母或数字0～9），则可以用D定义L的总的辞典顺序（lexicographic order，写成<L）：y短字符串在长字符串之前，即∀x(∀y((|x|<|y|)→(x<L y)))。

y长度相同时，用D按辞典顺序排列。

本书使用辞典顺序时，假设D是字母和数字的标准顺序。

如果D不明确，我们会指出。

程序辞典式枚举（lexicographically enumerates）L的元素的充分必要条件为按辞典顺序枚举。

例2.12辞典式枚举∈，b}*:all a’s precede all b’s}，则L的辞典式枚举如下：设L={x {aε, a, b, aa, ab, bb, aaa, aab, abb, bbb, aaaa, aaab, aabb, abbb, bbbb, aaaaa, ...本书第2部分、第3部分、第4部分用各种形式方法指定各类语言的语言生成器（枚举器）或语言识别器。

2.2.2 语言的势一种语言有多大？任何时候字母表的最小语言是∅，其势（Cardinality）为0。

任何字母表∑的最大语言是∑*。

什么是|∑*|？假设∑=∅，则∑*={ε}，|∑*|＝1。

如果∑不是空呢？定理2.2 ∑*的势定理：如果∑≠∅，则∑*是可计数的无限集。