李忠武 保山学院 云南保山 678000



正规文法与有穷自动机的等价性研究

李忠武 保山学院 云南保山 678000

【文章摘要】

正规表达式首先由Keene在20世纪50年代开始研究。McCullough和Pitts提出了一种描述神经活动的有穷自动机模型，从此以后，正规表达式和有穷自动机在计算机科学中得到了广泛应用。通常，对于正规文法G 和有限自动机M ，M 所定义的语言记作L（G），M 所能识别的语言记作L（M），如果有L（G）=L（M），则称G 和M是等价的。

【关键词】

正规式；正规文法；构造方法；等价性；有限自动机

引言

正规表达式的递归定义

（2）如果a是∑上的一个符号，那么a是一个正规表达式，并且。也就是说，这个语言仅包含一个长度为1的符号串a 。

（3）假定U和V都是∑上的正规表达式，分别表示语言为L（U）和L（V），那么，U |V、 U·V和（U）*也都是正规式，它们所表示的正规集分别为L（U）∪L（V）、L（U）L（V）（连接积）和（（闭包）

仅由有限次使用上述三步骤而定义的表达式才是∑上的正规式。

有穷自动机的定义

有限自动机是识别器，只能对每个可能的输入串简单回答“是”或“否”。它分为不确定的有穷自动机和确定的有穷自动机。

正规文法的概念

文法G 可定义为四元组，其中VN为非终结符的集合，VT为终结符的集合，P 为产生式的集合，S 为开始符号。若P 中的每个产生式的形式都是或A→a，其中A、B都是非终结符，a∈VT*，则G 是正规文法。

1　正规文法与有限自动机的等价性

对于正规文法G 和有限自动机M ，如果L（G）=L（M）f，则称G和M是等价的。

关于它们两者的等价性，有以下结论：

1.对于每一个右线性正规文法G或左线性正规文法G ，都存在一个有限自动机，使得L（M）=L（R）。……