问题
单项选择题
已知∑=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)*的非确定的有限自动机的过程如下所示。
[*]