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

admin2009-02-15 30

问题已知∑={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)