已知∑={0,1}上的正规表达式0*1(0|10*1)*,它和下列哪个图的NFA等价,(27)。

admin2009-02-15  12

问题 已知∑={0,1}上的正规表达式0*1(0|10*1)*,它和下列哪个图的NFA等价,(27)。

选项 A、
B、
C、
D、

答案B

解析 对于任一正规表达式R,可按如下方法构造出与之等价的非确定的有限自动机。
   ①对于正规式R,可用下图所示的拓广状态图表示。
         
   ②通过对正规式R进行分裂并加入新的结点,逐步把图转变成每条弧上的标记是∑上的一个字符或ε,转换规则如下图所示。
      
最后所得的图即为一个NFA M,x为初态结点,y为终态结点。显然,L(M)=L(R)。按照上述方法构造正规表达式0*1(0|10*1)*的非确定的有限自动机的过程如下所示。
转载请注明原文地址:https://kaotiyun.com/show/c3xZ777K
0

相关试题推荐
最新回复(0)