识别幺半群直积的最少状态DFA

黎宏伟

(宿迁学院 文理学院,江苏 宿迁223800)

1 概述

能够被确定有穷自动机（简称DFA）识别的语言称为正规语言。文[1]定义正规语言中的乘法运算为字符串的毗连。识别正规语言的DFA一般不唯一。文[2]定义：在识别一个语言的所有DFA中，有一个初始状态，且终结状态最少的DFA称为识别这个语言的最少状态DFA。若存在正规语言到半群S的同态满射，本文中也称能够识别这个正规语言的DFA可以识别半群S。文[3]证明了当每个幺半群只有一个R类时，识别这些幺半群强半格的最少状态DFA的终结状态的个数等于幺半群的个数。文[4]证明了识别完全单半群S=M（G；I，Λ；P）的最少状态DFA的终结状态的个数等于I中的元素的个数。本文中利用句法半群来证明识别两个幺半群A1和A2的直积的最少状态DFA的终结状态的个数等于识别这两个幺半群A1和A2的最少状态DFA的终结状态的个数的乘积。

2 预备知识

设∑为有穷字母表，令∑+表示∑上的所有非空字符串组成的集合，∑*表示∑上的所有字符串组成的集合（包括空字ε）[3]。建立在有穷字母表∑上的有限状态自动机（Q，∑，δ，q0，F）是一个五元组：Q是一个有穷的状态集合，∑是输入字母表，q0是初始状态且q0∈Q，F⊆Q是终结状态集合，δ是转移函数，它将Q×∑映射到Q，也就是说，输入字母a，自动机由状态q进入状态δ（q，a）。称自动机可以识别字符串w，若输入w后自动机从初始状态进入一个终结状态。能够被有限状态自动机识别的语言（集合）称为正规语言（集合）。定义∑+中字符串的运算为字符串的连接。

能够被有穷自动机（简称FA）识别的语言（集合）称为正规语言（集合）。一个FA称为DFA，若对于字母表∑中的任一字母a和FA中的任一状态p，从p出发标记为a的转移至多只有一个。文[1]指出能够被一个FA识别的语言一定能够一个DFA识别，一个语言L是正规语言的充要条件是L能被一个FA识别，或者被一个DFA识别。

设S是半群，1是半群S之外的元，定义S1=S∪1，且对于S中的任意元s，有s⋅1=1⋅s=s。半群的R类是一种重要的代数关系。由[4]知对于半群S中的任意两个元s和t，sRt当且仅当sS1=tS1。文[2]定义了一种特殊的等价关系，即右不变等价关系。设RL是语言L中的等价关系，x，y，z是L中的任意字符串，若xRLy⇒xzRLyz，则称RL是右不变等价关系。利用右不变等价关系可以判断语言L是否可以被一个DFA识别。

设D是A*的一个正规子集，且存在D到半群S的满同态映射θ。设a是字母表A中的字母，若am∈D，则直接记作am∈S，而这样的表示方式在下面的证明中不会出现任何矛盾。

文[3]给出了完全单半群的定义。设I和Λ是非空集合，G是幺半群，P是G上的Λ×I矩阵，在集合S=B×I×Λ上定义运算如下：

(a, i, λ )(b, j, μ ) =( ap b, i,μ)

其中P=[pλi]，pλi∈G，λ，μ∈Λ，i，j∈I，则S关于此运算构成半群，称为完全单半群，记作S=M（G；I，Λ；P）。本文以下设半群S是完全单半群，且Λ是有限集合。

3 引理

引理1[4]设半群S=M（G；I，Λ；P）是完全单半群，（a，i，λ），（b，j，μ）∈S则（a，i，λ）R（b，j，μ）当且仅当i=j。

由引理1显然可以得到下面的结论:

引理2完全单半群S=M（G；I，Λ；P）中的R类的个数就等于I中的元素的个数。

引理3完全单半群S=M（G；I，Λ；P）中的R关系是右不变等价关系。

证明.由文[4]知完全单半群S=M（G；I，Λ；P）中的R关系是右同余，因此是右不变等价关系。

引理4[2]下面两个命题是等价的：

（1）语言L∈A*被某个FA识别；

（2）L是一个右不变等价关系的并集，且这个等价关系具有有穷指数。

引理5前面所定义的完全单半群S=M（G；I，Λ；P）一定可以被某个DFA识别。

证明.设语言L∈A*且存在从L到半群S的满同态映射。由引理2和3知半群S是有限个R类的并集。

又由引理4知R关系是右不变等价关系，因此，S是有限个右不变等价类的并集。由语言L和半群S的关系显然可得L是有限个右不变等价类的并集。根据引理4，语言L被某个FA识别。于是L是正规语言，进而可得L被某个DFA识别。由前面的定义知半群S一定可以被某个DFA识别。

引理6[2]在同构(即状态重新命名)的意义下，识别一个语言的最少状态自动机是唯一的。

引理6说明从抽象的意义上看，识别半群S的最少状态DFA是唯一的。文[2]给出了求最少状态DFA的方法。设M=（Q，∑，δ，q0，F）是识别语言L的DFA。令M'=（Q'，∑，δ'，[q0]，F'），其中Q'=[q]，且q是从q0可以到达的；F'={[q]，且q在F中；δ'（[q]，a）=δ'（q，a）。

引理7[2]上面构造的自动机M'是识别语言L的最少状态DFA。

4 结论与证明

本文主要证明一个定理

定理1设I是有限集合，识别完全单半群S=M（G；I，Λ；P）的最少终结状态DFA的终结状态的个数等于I中的元素的个数。

证明.定义自动机M=（Q，∑，δ，q0，I），其中q0是初始状态，I是终结状态集合。M识别S中字符串的方式为：若字母w=（a，i，λ），则输入w后，自动机从初始状态q0进入终结状态i；在状态i输入字母w=（a，i，λ）后，自动机还是进入终结状态i；在状态i输入字母v=（a，j，μ）后，自动机进入终结状态j。显然，M刚好识别半群S。由于I中的元的个数是有限个，故M是FA。下证M是DFA。

在初始状态q0输入字母表A中的任一字母w=（a，i，λ）后，自动机从初始状态进入终结状态i，且不会进入其它终结状态。因此，从q0出发标记为w=（a，i，λ）的转移有且只有一个。在终结状态i输入w=（a，i，λ）之后，自动机仍然从状态i进入终结状态i，且不会进入其它终结状态。因此，从i出发标记为w=（a，i，λ）的转移有且只有一个。由前面的定义知，在其它终结状态j输入字母w=（a，i，λ）后，自动机从状态j进入终结状态i，且不会进入其它终结状态。因此，从其它终结状态j出发标记为w=（a，i，λ）的转移也是有且只有一个。综上，在自动机M中任一状态输入w=（a，i，λ）之后，从这个状态出发标记为w=（a，i，λ）的转移至多只有一个，故M是DFA。

下面按照前面介绍的方法构造识别半群S的最少状态DFA。令M'=（Q'，∑，δ'，[q0]，F'），其中Q'=[q]，且q是自动机M中从q0可以到达的状态；F'={[q]}，且q是自动机M中包含在I中的状态；δ'（[q]，a）=δ（q，a）。在自动机M中从q0可以到达的状态当然包括q0本身，另外，从q0可以到达所有的状态I，因此Q'中的状态数等于集合I∪{q0}中的状态数，F'中的状态数等于I中的状态数。综上，识别半群S的最少状态DFA的终结状态的个数等于I中幺半群的个数。定理1得证。

推论 从同构的意义上看，前面定义的自动机M=（Q，∑，δ，q0，I）就是识别半群S的最少状态DFA。