RE到FA的自动机转换

2022-04-15 自动机教程 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编写一个过渡表。

州	0	1
→q0	第3季	{q1, q2}
q1	f	?
q2	?	第3季
q3	第3季	f
*qf	?	?

等效的DFA为：

州	0	1
→[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：

文章图片

推荐阅读

上一篇：2022年4月15日，第8天

下一篇：Arden定理