正则表达式和有限自动机.doc

语言与计算理论导引 正则表达式和有限自动机第二部分 正规语言和有限自动机语言往往是无限集，但描述的方法往往是有限的，一种方法是描述如何通过字符串操作由简单的字符串产生整个语言，或者描述如何通过集合操作由简单语言产生复杂语言。另一种方法是描述识别字符串是否属于某个语言的机制，也就是描述一个算法过程。本书考察的最简单的语言类是正规语言，正规语言能够通过应用有限次的某个标准操作从一元语言产生。正规语言能够被有限自动机识别，有限自动机是空间严格受限的简单机器。在第二部分，我们还考察正规语言的另外一些特点：1）导出将一种语言的描述翻译成另一种语言的描述的算法；2）使用形式化方法描述语言；3）正规语言在实际中的应用。3 正则表达式和有限自动机3.1 正则语言和正则表达式注意：regular language和regular expression有时也翻译成正规语言和正规表达式。正则语言可以从非常简单的表达式得到，初始语言的字符串为空或单字母，仅使用合并、连接和Kleene连接运算，因此正则语言可用一个清楚的表达式描述，通常用小括号()代替大括号，+代替，称为正则表达式。下面是一些定义在字母表0, 1上的正则表达式，通过这些例子，能够感受到书写正则表达式的一些规律。语言相应的正则表达式LL00001或0010010, 1或010+10, 10或0100+101, L001(1+L)001110*0, 1(110)*(0+1)1*101*1010, 111, 11010*(10+111+11010)*0, 10*(11*001, L)(0+10)*(11)*+001+L)我们认为正则表达式表示的是相应语言的“最典型的字符串”，比如，1*10表示一个字符串，它以10结束，前面可以有任意多个数目的1。我们在前面将正则语言描述成：在最简单的语言上仅仅使用三种运算合并、连接、Kleene连接所得到的语言。这种描述预示了正则语言的递归定义（参见2.4节）。下面递归定义不仅定义了语言，而且定义了正则表达式。定义3.1 字母表上正则语言类R，及其相应的正则表达式定义如下：1. 空集f（即空语言）是正则语言，表达式是f。2. L 仅有空串的语言是正则语言，表达式是L。3. 每个a，a是正则语言，表达式是a。4. 如果L1和L2是正则语言，表达式是r1和r2，则(a) L1L2是正则语言，表达式是r1+r2。(b) L1L2是正则语言，表达式是r1r2。(c) L1*是正则语言，表达式是r1*。只有应用上面4条规则产生的语言才是字母表上的正则语言。对上面的解释做些解释。为了保持一致性和连贯性，空语言被认为是正则语言。后面许多地方将提到这样的说法：对于每个，都对应一个正则语言。如果空语言不属于正则语言，那么每个这样的说法还需要排除空语言这种特殊情况，带来不简洁的说法。为了书写简洁，省去大量的括号，我们规定正则表达式中运算符的优先级次序是Kleene*、连接、合并。同时我们借用一些代数表达式的符号，如指数幂等。原表达式简洁表达式(rr)r2(a+(b*)c)a+b*c(r*)r)r+同样借助代数学的记号，两个表示不同语言的正则表达式可以使用符号，比如：(a + b)* a + b*我们还可以借用符号=来化简正则表达式，如正则表达式的化简1*(1+L) = 1*1*1* = 1*0* + 1* = 1* + 0*(0*1*)* = (0+1)*(0+1)*01(0+1)*+1*0*=(0+1)*其中一些化简用到的规则可以从集合运算规则得到，但另有一些是字符串运算特有的，目前我们还没有发现这种化简的系统的方法（或形式化方法），但上面的例子预示了化简的巨大作用。比如最后一行的例子，两个看似很复杂的语言，它们的并集却很简单。问题：存不存在化简正则表达式的形式化方法（既是否存在化简正则表达式的通用算法）？是否存在最简洁的正则表达式？朱洪来信：我的印象中，它是NP-完全的问题。Please look at Garey and Johnsons book: computer and intractibility.例子3.1 语言L0, 1*，由所有长度为偶数的字符串组成，（由于0是偶数，因此空串L属于L），问：L是否是正则语言？如果是，L对应的正则表达式是什么？解答：任何一个偶数长度的字符串都由多个（或0个）长度为2的字符串连接而成，而字母表0, 1上的长度为2的字符串只可能是4个：00、01、10、11，因此L可定义如下：L=00, 01, 10, 11*它的正则表达式是：(00+01+10+11)*或(0+1)(0+1)*。例子3.2 L是定义在字母表0, 1上的包含奇数个1的字符串组成的语言，问L的正则表达式是什么？解答：显然L中的字符串至少有一个1，因此一定有这样的前缀0i10j，其后则有偶数个（或0个）1，因此可分解成多组10m10n的形式。由此得到L的正则表达式：包含奇数个1的字符串组成的语言0*10*(10*10*)*以最左的1为基准(10*10*)*0*10*以最右的1为基准(10*10*)*0*10*(10*10*)*以中间的某个1为基准0*1(0*10*1)*0*考虑最左1之后的后缀(0*10*1)*0*10*0*(10*10*)*1(0*10*1)*0*错误的表达式有：(10*10*)*10*例子3.3 L是字母表0, 1上所有长度小于等于6的字符串组成的语言，问L的正则表达式？解答：由于L中的元素是有限的，最简单的方法是枚举法：L+0+1+00+01+111110+111111而表示长度为n的字符串组成的语言的表达式是：(0+1)(0+1)(0+1)=(0+1)n因此一些简洁的表达式如下：所有长度小于等于6的字符串组成的语言L+(0+1)+(0+1)(0+1)+(0+1)(0+1)(0+1) (0+1)(0+1)(0+1)L+(0+1)+(0+1)2+(0+1)6(L+0+1)6例子3.4 L=x以1结束且不包含子串00 | x0, 1*，问L的正则表达式？解答：字符串不包含00，则说明其中的每个0不能后接0，而且0不能是串尾字母，因此每个0后面必定是1，既符合条件的字符串包含大量的01片断，其间是许多1，因此初步得到的表达式是：(1+01)*但空串不符合条件，修正得到：(1+01)*(1+01)=(1+01)+注意：(1+01)*1不对，漏掉了01情况。例子3.5 C语言的标志符的组成的语言的正则表达式。解答：C语言的标志符由3种符号组成：英文字母、数字和下划线。而且第一个字符只能是字母或下划线。因此：(a+b+z+A+B+Z+_)( a+b+z+A+B+Z+0+1+9+_)*我们令l是表示字母的集合，d是表示数字的集合，即：l = a+b+z+A+B+Zd = 0+1+9则上式的简洁表达式是：(l+_)(l+d+_)*例子3.6 （暂空）3.2 识别语言所需要的空间语言的识别（或字符串的识别，recognize）问题是一个成员资格判定问题，即判定一个任意给定的字符串是否属于某个语言。为了以后讨论问题的方便，给出一些约定。首先限制成从左至右的一次扫描（这简化了整个识别过程中应该记住的信息总量的讨论，也利于根据每步记住的信息量多少对语言分类），其次判别对象是一个特定的字符串。除了扫描完成后，给出最后的判别（是或否），在每一步也给出假设判别，当前的假设判别反映了已扫描的前缀的情况。最后的判别可以看成最后的、最新的假设判别。先看看人是怎么完成识别任务，然后设计自动机完成这项任务。问题是，为了给出假设判别，我们应该记住多少前缀信息。这里有两种极端的情况：1）记住所有的前缀2）什么也不记忆。在某些情况下，我们确实可以什么也不记，如判别语言f和*，前者我们忽略每步输入，一律回答“否”；后者则一律回答“是”。但多数情况下，我们必须记住一些信息，应该记住的不是字符串本身，而是字符串表达的判别信息。称为有限自动机的原因是所需的空间是有限的。比如分别输入两个字符串x和y，得到不同的答案。这说明我们一定记住了一些不同的信息当分别输入x和y时，否则我们无法区别这两个字符串，因此通常情况下，为了识别某个语言，我们必须记住一些信息，而记住这些信息则需要一定的空间。例子3.7 语言L定义在字母表0, 1上，由以10结尾的字符串组成。分析：显然判定（decision）一个字符串是否属于语言L，只需要考察该字符串的最后两个字符，因此在字符串输入识别过程中，只需要记住当前最后的两个字符，而之前的所有字符可以忽略。字母表0, 1上的两个字符组成的字符串只有4种，因此本例所需空间为4个单位，当然后面会看到还可进一步减少记住的信息，从而节省空间。例子3.8语言L定义在字母表0, 1上，由包含偶数个0和奇数个1的字符串组成。分析：显然，整个输入过程中，不需要记住输入的字符串的具体内容，一种方法是记住当前输入的0和1的个数，更简单的方法是记住当前输入的0和1的个数的奇偶性，而这只有4种可能，因此本例的判定过程所需空间是4个单位。（参见图3-1，77页）例子3.9 语言L=x以1结束且不包含子串00 | x0, 1*（参见例子3.4）分析：假设在当前输入的字符串中发现了00子串，则我们只需要记住这个事实，不管前面已经读过和后面将输入的字符串是什么，能够肯定该字符串不属于L，不妨将这种情况记为N。再考虑另两种情况，情况0是最后一个字符是0，情况1是最后一个字符是1。出现情况0时，如果又看到一个0，则转到情况N，而情况0和情况1时看到1都转到情况1，情况1时看到0转到情况0。这三种情况能够判定所有非空的字符串了，为了判定空字符串，还需要增加一个特殊的情况。显然所有的情况都专注于记住最后一个字符，和是否出现或有可能出现00子串。本例需要的空间是4个单位，参见图3-1。将例子3.8和3.9的讨论用一个图（图3-1）来总结，它像一个流程图，或展示了我们上面判定过程的算法。图中每个圆表示一种情况，是我们需要记住的关键信息，因此圆的多少表示了记住信息的多少，也表示了判定过程中需要的总的空间的多少。每个图中有一个起始的圆（由一个没有源的箭头指示），输入的字符串从起始圆开始，沿着箭头流动（转移）到下一个圆，每一次流动消耗一个字符，当字符消耗完（即读完所有字符），所停在的圆揭示了输入字符串与图表示的语言的关系，如果圆是双圈，则说明该字符串被接受，或属于这个语言，否则不属于这个语言。有了这样的图后，任何人或机器不用理解图中每个节点的具体含义，只要按照上面描述的机械的步骤动作，就能完成字符串的判定工作，因此刻画了一种“抽象机”，我们不关心这种机器的实现细节，比如它的驱动动力来自什么，它表示接受的具体信号是什么？我们关心的是它所揭示的一种形式化的过程（或算法），我们称它为自动机。将要证明能够被这种自动机识别的语言是正则语言，下面的例子显示存在语言无法被这种自动机识别，因此存在非正则语言，而且我们将来的结论是非正则语言大量存在，尽管3.1节显示的正则表达式具有灵活且强大的描述能力。例子3.10 语言L是例子2.16中描述的回文语言pal。分析：L的每个字符串相同于它的反写字符串，因此从描述上看，这似乎是一种很简单的语言，但是从判定过程所需要的空间而言，它完全不同于例子3.7到3.9中的语言。对于任意两个不同的字符串x和y，都存在一个字符串z，使得xz属于L，而yz不属于L（证明见后），因此需要区别的字符串是无穷多，自动机需要的空间是无穷多，因此L不是有限自动机能够识别的语言。分三种情况讨论：1. x和y长度相同，则令z=xr；2. x比y短，设y=y1y2，其中y1与x同长，令z=wwrxr，且wy2，则xz是回文，而yz不是回文。3. 类似情况2。形式化的方法（即从计算机的角度）定义语言的复杂程度，而不是人脑的感觉来判定语言的复杂程度，一些人脑感觉简单的语言，如回文，可能是计算机认为的复杂语言；反过来，一些计算机容易处理的语言却可能是人脑难以把握的。另外，计算机定义语言是从判定的角度，而不是从语言的产生或大小等等角度进行的。3.3 有限自动机（finite automata）从3.2节的例子很容易导出有限自动机的正式定义。定义3.2：有限自动机（finite automata, FA）是一个5元组（Q, , q0, d, A），其中1）Q是一个有限集，其元素称为状态。2）是有限字母表，其元素是输入符号。3）q0Q，是初始状态。4）AQ，是接受状态集。5）d是转移函数，从Qx到Q。这种定义在其他数学概念定义中很少见，数学家R. P. Boas曾在发表在the American Mathematical Monthly的题为Can We Make Mathematics Intelligible?的文中写到：There is a test for identifying some of the future professional mathematicians at an early age. There are students who instantly comprehend a sentence beginning “Let X be an ordered quintuple (a, T, p, a, b), where” They are even more promising if they add, “I never really understood it before.”但这是计算机科学，尤其是形式语言和自动机理论中很喜爱采用的定义形式，很象是描述了一个机器的5个部件，或程序设计语言中对象的定义。且不管它的数学含义，或是否一个5元组如何成为一个机器，它确实提供了一个有效的标记方法。例子3.11（例子3.7的进一步讨论）画出识别语言L=0, 1*10的有限自动机。见图3-2。我们可以简化图3-2所示的FA。考虑状态0和状态00，它们都不是接受状态，而且无论下一个字符是0还是1，都进入同一个状态（0进入状态00，1进入状态01），因此状态0和状态00可以合并（不妨称为A），不会改变自动机识别的语言。同理，状态1、状态01和状态11能够合并成一个状态（不妨称为B），更进一步，新状态A可以和状态L合并。最后简化后的自动机只有3个状态，见图3-3。简化后的自动机显然更简洁和深刻地体现了语言的本质特征，图3-3中的状态B含义是发现当前字符为1，满足了10结尾的一半要求，状态10则表示满足了全部要求。正如正则表达式可以简化，有限自动机也可以简化。寻找简化的形式化方法。删除有限自动机的死状态是简化的一个有效方法。例子3.11的简化方法存在形式化的方法，5.2节会具体介绍。前面提到了自动机的状态转换，定义了输入一个字符的转移函数，下面形式化定义输入字符串的转移函数，很容易想到递归定义，首先需要知道字符串的递归定义。显然字符串递归定义的起点是空串L，长度为n的字符串由长度为n-1的前缀和最后一个字符构成，即x=ya。定义3.3 M=（Q, , q0, d, A），函数d*的递归定义：1）qQ，d*(q, L)=q2）d*(q, ya)= d(d*(q, y), a)讨论，也可以认为长度为n的字符串由第一个字符和长度为n-1的后缀构成，即x=ay。则定义3.3的递归部分也可以写成：2）d*(q, ay)= d*(d(q, a), y)但通常认为定义3.3使用更方便。根据图3-4的自动机，计算d*(q, abc)。解答1：d*(q, abc) = d(d*(q, ab), c)= d(d(d*(q, a), b), c)= d(d(d*(q, La), b), c)= d(d(d(d*(q, L), a), b), c)= d(d(d(q, a), b), c)= d(d(q1, b), c)= d(q2, c)= q3解答2：d*(q, abc) = d*(q, abc)= d*(d(q, a), bc)= d*(q1, bc)= d*(d(q1, b), c)= d*(q2, c)= d*(d(q2, c), L)= d*(q3, c)= q3根据定义3.3，有如下的结论：1. d*(q, a) = d(q, a)，a是单个字符2. d*(q, xy) = d*(d*(q, x), y)，x、y是字符串，可以用数学归纳法证明，参见练习3.25有了字符串转移函数的定义，我们能够形式化定义什么是自动机接受的字符串和自动机接受的语言。定义3.4 存在自动机M=（Q, , q0, d, A），字符串x被M接受当且仅当d*(q0, x)A，否则称为x被M拒绝，被M接受或识别的语言是，L(M)=x|x被M接受。字母表上的语言L，被自动机M接受（accepted）或识别（recognized）的充分必要条件是L=L(M)。注意：此处没有区分接受（accepted）和识别（recognized）这两种提法。有限自动机接受的语言是由所有被M接受的字符串组成，而不是部分。有限自动机的能力不体现在它的状态数，不体现在它能接受的字符串的个数，体现在它的鉴别能力，它接受什么样的字符串，拒绝什么样的字符串。如果给定一个语言L，构造接受L的自动机M，它接受所有属于L的字符串，拒绝所有不属于L的字符串，而不仅仅是接受属于L的字符串，否则图3-5所示的自动机接受所有的语言，失去了自动机研究的意义。定理3.1 一个语言是正则语言当且仅当被一个有限自动机接受。（Kleene定理，后面证明）定理3.1揭示了，一方面，给定一个有限自动机M，存在一个正则表达式E表示M所接受的语言，即L(M)=L(E)；另一方面，给定一个正则表达式E，存在一个有限自动机接受E所表示的语言。第4章Kleene定理的证明将给出构造正则表达式和有限自动机的形式化方法。这里先给出一些仅凭直觉就能解决的简单例子，有助于导出最后的形式化方法。例子3.12 参见图3-6，构造它接受语言的正则表达式。分析：逐个分析自动机的每个接受状态，然后分析接受状态的所有到达路线。本例有两个接受状态A和B，状态A接受的语言是(00)*，状态B接受的语言是(00)*11(11)*，则整个自动机接受的语言是：(00)*+(00)*11(11)* = (00)*(11)*例子3.13 考虑图3.7所示的自动机。分析：先找到自动机接受的最短的字符串，baaa，进一步发现所有的状态读入b都会转入状态B，从起始状态A到达接受状态E的路径只有一条，即ABCDE，因此此自动机接受的字符串的特征是以baaa结尾，得到正则表达式如下：(a+b)*baaa另一种思考方法是从起始状态开始，考虑到达其他状态所对应的正则表达式，每一次转移预示一个连接操作，每一次分支，预示一个合并操作，每一次循环，预示一个Kleene连接操作。ABCDEAabBbaCbaDbaEabABCDEAa*bBb*aCbaDbaEabABCDEAa*bb*a*bb*aBb*aCbaDbaEabABCDEAa*bb*a*bb*aa*bb*aaBb*aCbaDbaEabABCDEAa*bb*a*bb*aa*bb*aaa*bb*aaaBb*aCbaDbaEabABCDEAa*bb*a*bb*aa*bb*aaa*bb*aaaBb*b*(ab)*ab*aab*aaaCbb*bb*aaDbb*bb*abb*aaa+bb*aaaEabb*bb*(ab)*aABCDEAa*bb*a*bb*a(bb*a)*a*bb*aaa*bb*aaaBb*b*(ab)*ab*aab*aaaCbb*bb*aaDbb*bb*abb*aaa+bb*aaaEabb*bb*(ab)*a往往是循环里面有循环，分支里面有分支，循环里面有分支，分支里面有循环，这样产生的表达式将会很复杂。因此目前形式化方法得到的正则表达式并不实用，有赖进一步发现简化的方法。先给初始状态赋初值，然后扩展到其他状态，然后反馈回来，反复迭代计算，直到最后稳定下来，计算停止，一个关键点是如何比较两个正则表达式。例子3.14 反过来，给定正则表达式r=(11+110)*0，构造有限自动机接受语言L(r)。分析：空串不属于语言L，因此初始状态q0不是接受状态，0属于语言L，因此存在从初始状态到接受状态标记为0的转移。另外，1和L是可区分字符串（存在字符串110，使得1110被拒绝，而110被接受），因此输入1和L，状态q0应该到达不同的状态，称输入1后的状态为r，因此至少存在3个状态，见图3-8a。如果字符串前缀为0或10，则无论后续字符串是什么，都不属于语言L，引入一个状态s，记录字符串判定中到达失败状态，一旦到达s，则不再离开。继续分析状态r，由于字符串1和11是可区分的（利用字符串10），而且11与0和L都是可区分的，因此需要再加一个状态t，同样发现可区分字符串110，增加状态u，这样得到两个接受状态。我们发现没有新的可区分状态了，因此不用再添加状态了，剩下的任务就是完善各个状态的转移函数。上面的方法称为hit-or-miss，只要需要，就添加新状态，直到不再添加新状态，构造自动机的过程才停止。定理3.1保证了构造正则表达式表示的语言的自动机的过程能够最终完成，即状态数是有限的。现在方法的最大难点是判断是否需要加入新状态，如果不需要，那么哪个已有状态是合适的？第4章描述的形式化方法将避开这个难点。3.4 区别字符串利用有限自动机识别语言的基础是自动机不需要区分所有的字符串，不需要在识别过程中记住前缀的具体内容，正如上节例子显示，自动机状态用来区分那些需要区分的字符串。有限自动机仅仅判别字符串是否属于某个语言，不需要区别不同的字符串，因此不需要记住输入的整个字符串。有限自动机不同状态的数目与不同字符串的数目相关。下面我们形式化这种思想，并揭示状态数与区分字符串数之间的关系。定义3.5 给定字符串x和y，如果存在字符串z，使得xz和yz只有一个属于语言L，则称z在语言L上区分x和y。如果不存在z，则称x和y在L上是不可区分的。根据定义3.5，如果x和y是不可区分的，则对任意的字符串z，xz和yz到达同样的状态，同时被接受，或同时被拒绝。例如语言L=x0, 1* | x以10结尾（参见例子3.7），字符串01011和100在L上是可区分的，因为存在z=0，区分这两个字符串，而0和100是不可区分的。引理3.1 M=(Q, , q0, d, A)识别语言L，如果字符串x和y，d*(q0, x)=d*(q0, y)，则x和y在L上不可区分。证明：设z是上的任意一个字符串，分别考察xz和yz，根据练习3.25，d*(q0, xz)=d*(d*(q0, x), z)d*(q0, yz)=d*(d*(q0, y), z)根据条件，d*(q0, xz)= d*(q0, yz)可见xz和yz要么同时被M接受，要么同时被拒绝，因此x和y在M所识别的语言L上是不可区分的。定理3.2 假设n个字符串在语言L上两两可区分，那么识别L的有限自动机的状态数不少于n。证明：设这n个在L上两两可区分的字符串是x1, x2, , xn，存在一个识别L、状态数小于n的自动机M，那么根据鸽笼法则，d*(q0, x1)、d*(q0, x2)、d*(q0, xn)中必定存在i和j，使得d*(q0, xi)= d*(q0, xj)。根据引理3.1，xi和xj不可区分，与前提矛盾，即假设不成立，状态数少于n的识别L的有限自动机不存在。定理3.2提供了一个估计有限自动机状态数下限的办法。同时如果能够证明语言L有无穷个可区分的字符串，则说明L不是有限自动机能够接受的语言，也不是正则语言。例如回文语言就不是正则语言。例子3.15 语言Ln=x0, 1* | |x|=n，且从右数起的第n个字符为1分析：一个直观的方法是，给每个长度小于等于n的字符串构造一个状态（参见例子3.11），这样自动机能够记住当前输入字符串的最后n个字符，当然也记住了倒数第n个字符。长度为n的字符串共有2n个，那么长度小于等于n的字符串共有：20+21+2n=2n+1-1这就是总的状态数，图3-9显示了识别n=3的语言的自动机，它的转移函数很简单：d(abc, d)=bcd也许其他方法能够发现更简单（状态数大大少于2n+1-1）的自动机，但根据定理3.2我们能够证明接受语言Ln的自动机至少需要2n个状态，因为长度为n的字符串在Ln上两两可区分，即至少存在2n个可区分的字符串。设x和y是两个长度为n的不同的字符串，它们在从右数第i个字符不同（1=i=n），任意选取一个长度为n-i的字符串z，则xz和yz的右数第n个字符不同，因此有且只有一个属于语言Ln，x和y可区分。定理3.2保证了识别某个语言L的任何自动机的状态数不少于某个常数，如果对任何一个常数n，都能证明任何识别L的自动机的状态数都不少于n，则说明在L上存在无限多的可区分字符串，没有有限自动机能够识别它，这种语言也不是正则语言。反过来，如果能够证明L上有无限多个可区分字符串，就能证明不存在接受L的有限自动机，L不是正则语言。引申例子3.10，我们得到定理3.3，这也是我们显示的第一个非正则语言。定理3.3 字母表0, 1上的回文语言pal（palindromes）是非正则的。证明：根据例子3.10，字母表上的任何两个字符串都是可区分的，因此存在无限多的可区分字符串，根据定理3.2，pal不是正则语言。在第5章，我们考察其他一些非正则语言，并提出其他方法去判定语言的正则性，定义3.5将再次出现，可以用来很好地描述“最小状态”自动机的概念。3.5 并集、交集和补集设L1和L2都是字母表上的正则语言，则存在有限自动机M1和M2分别接受L1和L2（根据定理3.1），同时另外三种语言L1L2、L1L2和L1*也是正则语言（根据定义3.1），因此也存在接受这三种新语言的有限自动机，一个问题很自然提出来：接受新语言的有限自动机能否根据M1和M2构造出来？有关连接和Kleene连接运算的问题我们到第4章后再讨论，此处讨论合并运算，容易看到，合并运算的处理方法稍作修改就能处理交集和差集运算。设M1=(Q1, , q1, d1, A1)且M2=(Q2, , q2, d2, A2)，现在要构造FA M接受语言L1L2，显然如果M在识别字符串x的每一步都能记住足够多的信息，并最终知道x与L1和L2的关系，那么M就能判定x与语言L1L2的关系。我们可以将M的状态设计成一个二元组(p, q)，用它来同时跟踪M1和M2的状态转移，其中pQ1，qQ2，(p, q)Q1Q2，M的初始状态是(q1, q2)，分别来自M1和M2的初始状态，M的转移函数定义如下：d(p, q), a)=(d1(p, a), d2(q, a)现在我们来确定接受状态集。x被M接受，即它或者被M1接受，或者被M2接受