个性化阅读
专注于IT技术分析

RE到FA的自动机转换

点击下载

要将RE转换为FA,我们将使用一种称为子集方法的方法。此方法用于从给定的正则表达式获取FA。该方法如下:

步骤1:使用带有NF动作的NFA设计给定正则表达式的转换图。

步骤2:将此带ε的NFA转换为不带ε的NFA。

步骤3:将获得的NFA转换为等效的DFA。

范例1:

根据给定的正则表达式10(0 11)0 * 1.设计一个FA。

解决方案:首先,我们将为给定的正则表达式构造过渡图。

步骤1:

第2步:

第三步:

步骤4:

步骤5:

现在我们得到了不带ε的NFA。现在,我们将其转换为所需的DFA,首先将为此NFA编写一个过渡表。

01
→q0第3季{q1, q2}
q1fϕ
q2ϕ第3季
q3第3季f
*qfϕϕ

等效的DFA为:

01
→[q0][q3][q1, q2]
[q1][qf]ϕ
[q2]ϕ[q3]
[q3][q3][qf]
[q1, q2][qf][qf]
*[qf]ϕϕ

范例2:

根据给定的正则表达式1(1 * 01 * 01 *)*设计NFA。

解决方案:给定正则表达式的NFA如下:

步骤1:

第2步:

第三步:

范例3:

为正则表达式0 * 1 10构造FA。

解:

我们将首先为R = 0 * 1 10构造FA,如下所示:

步骤1:

第2步:

第三步:

将RE转换为FA

步骤4:


赞(0)
未经允许不得转载:srcmini » RE到FA的自动机转换

评论 抢沙发

评论前必须登录!