构造带 Epsilon 转换的 NFA，正则表达式为 a+ba*。

正则表达式 R= a+ba* 分为 r1 和 r2

r1= a 和 r2= ba*

我们来绘制 r1 的非确定有限状态自动机 (NFA)，如下所示 -

现在，我们从 r2 = ba * 开始

将 r2 分为 r3 和 r4，其中 r3=b 和 r4=a*

r3 的 NFA 如下 -

r4 的 NFA 如下 -

q5 通过 epsilon 转换到 q6 和 q8，q6 通过 'a' 转换到 q7，而 q7 通过 epsilon 转换到 q6 和 q7。

r2= r3.r4

现在，连接 r3 和 r4，如下所示 -

q3 输入 'b' 后进入 q4，q4 通过 epsilon 转换到 q5，q5 通过 epsilon 转换到 q6，q6 输入 'a' 后进入 q7，而 q7 通过 epsilon 转换到 q6 和 q8。

现在，组合所有表达式，即 R=r1+r2 =a+ba*，如下所示 -

上图为给定正则表达式 a+ba* 的最终 NFA 带转换。

Bhanu Priya

更新日期： 12-6 月 -2021

8K+ 浏览

开启你的 职业

完成课程，获得认证

开始