有穷自动机到正规式的转换
有穷自动机到正规式的转换
将转换图的概念加以拓广,令其中的每条弧都可以用一个正规式标记,具体方法如下。
首先,在 M 的转换图上添加两个结点: X 结点和 Y 结点,从 X 结点用 ε 连线连接到 M 的所有初态结点,从 M 的所有终态结点用 ε 连线连接到 Y 结点,从而构成一个新的非确定有穷自动机 M’ ,它只 有一个初态结点 X 和一个终态结点 Y 。显然,L ( M ) = L ( M’ ),即这两个 NFA 是等价的。然后,逐步消去 M’ 中的其他结点,直至只剩下 X ,Y 结点。在消除结点过程中,逐步用正规式来标记相应的箭弧。消除结点的过程是很直观的,只需反复使用图 3.18 的替换规则即可。
例 3.18 】设有穷自动机的状态图如图 3.19 所示,试求该自动机识别语言的正规式。
分析 首先加进 X 结点和 Y 结点,形成如图3.20 ( a )所示的状态图,然后消去 U 结点和 V 结点后得到如图 3.20 ( b )所示状态图,进一步消去 S 结点和 Z 结点得到如图 3.20 (c )所示状态图。所以该自动机识别语言的正规式为R = ( 10|01 )( 10|01 )*