从给定的正则表达式设计有限自动机。

有限自动机 (FA) 是一种抽象的计算设备。它可以用以下方式表示：

• 图形化（状态转换图）
• 表格化（状态转换表）
• 数学化（状态转换函数）

FA 的正式定义是它是五元组。

M=(Q, Σ, δ, q0, F)

其中，

• Q：称为状态的有限集合
• Σ：称为字符集的有限集合
• δ：Q × Σ → Q 是状态转换函数
• q0 ∈ Q 是起始或初始状态
• F：结束或接受状态

正则表达式

正则表达式可用于描述定义字符串的一系列模式。它用于匹配字符串中的字符组合。

某些正则表达式接受的语言称为正则语言

现在让我们考虑 **RE 10+(0+11)0*1**，

为该正则表达式构建有限自动机：

步骤 1

最初考虑两个状态 q0 和 qf。此外，考虑初始和最终状态，q0 到 qf 和给定的正则表达式 10+(0+11)0*1

步骤 2

现在应用并集运算，q0 上的 10 转到 qf，q0 上的 (0+11)0*1 转到 qf。

步骤 3

现在，通过应用连接来划分表达式，即设 L1=0，L2=1。连接两者，我们得到 L= L1.L2。

将此公式应用于正则表达式，因此 q0 上的 1 转到 q1，q1 上的 0 转到 qf。类似地，q0 上的 (0+1) 转到 q2，q2 上的 0*1 转到 qf。

步骤 4

q0 上的 1 转到 q1，q1 上的 0 转到 qf，q0 上的 (0+1) 转到 q2，q2 上的 0 转到 q2 本身，q2 上的 1 转到 qf。

步骤 5

给定正则表达式的最终有限自动机如下所示：

Bhanu Priya

更新于： 2021年6月12日

2K+ 次浏览

启动您的 职业生涯

通过完成课程获得认证

开始学习