黎宏伟

(宿迁学院 文理学院,江苏 宿迁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）识别的语言（集合）称为正规语言（集合）。……