问题 单项选择题

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

A.A

B.B

C.C

D.D

答案

参考答案:B

解析:

对于任一正规表达式R,可按如下方法构造出与之等价的非确定的有限自动机。

①对于正规式R,可用下图所示的拓广状态图表示。

[*]

②通过对正规式R进行分裂并加入新的结点,逐步把图转变成每条弧上的标记是∑上的一个字符或ε,转换规则如下图所示。

[*]

最后所得的图即为一个NFA M,x为初态结点,y为终态结点。显然,L(M)=L(R)。按照上述方法构造正规表达式0*1(0|10*1)*的非确定的有限自动机的过程如下所示。

[*]

单项选择题
问答题 简答题