数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学如何从有限自动机生成正则表达式？
将确定性有限自动机 (DFA) 转换为正则表达式 (RE) 有两种方法。它们如下所示：
- Arden 方法
- 状态消除法
让我们详细了解这些方法。
Arden 定理
设 P 和 Q 为两个正则表达式。
如果 P 不包含空字符串，则关于 R 的方程 R = Q + RP
其唯一解为 R = QP*
这里：
有限自动机没有 ε 移动
它必须只有一个初始状态 q1
其状态为 q1, q2, q3,……qn。最终状态可以是某个 qi，其中 i<=n
qi 是表示有限自动机接受的字符串集的正则表达式，即使 qi 是最终状态。
使用 Arden 定理求 DFA 的 RE
为了找到给定自动机的正则表达式，我们首先为所有状态创建如下所示的方程：
q1=q1α11+q2α21+----------+qnαn1+𝟄 q2=q1α12+q2α22+-----------+qnαn2 - - - - qn=q1α1n+q2α2n+------------+qnαnn.
通过重复应用替换和 Arden 定理，我们可以用 αij 来表示 qi。为了获得 FSA 识别的字符串集，我们必须取对应于最终状态的所有 qi 的并集。
示例
注意 - 对于并行边，该状态在表达式中将有多个表达式。
然后，我们求解这些方程以获得 qi 关于 αij 的方程，该表达式就是所需解，其中 qi 是最终状态。
q1 = qa + q3a + ε (ε 移动是因为 q1 是初始状态)
q2 = q1b + q2b + q3b
q3 = q2a
现在，我们将求解这三个方程
- q2 = q1b + q2b + q3b
q2 = q1b + q2b + (q2a)b (代入 q3 的值)
q2 = q1b + q2(b + ab)
q2 = q1b(b + ab)* (应用 Arden 定理)
- q1 = q1a + q3a + ε
q1 = q1a + q2aa + ε (代入 q3 的值)
q1 = q1a + q1b(b + ab)*aa + ε (代入 q2 的值)
q1 = q1(a + b(b + ab)*aa) + ε
q1 = ε(a + b(b + ab)*aa)*
q1 = (a + b(b + ab)*aa)*
因此，正则表达式为 (a + b(b + ab)*aa)*。
状态消除法
步骤 1
DFA 的初始状态没有任何入边。
如果初始状态存在任何入边，则需要创建一个没有入边的新的初始状态。
示例
步骤 2
DFA 中必须只有一个最终状态。
如果 DFA 中存在多个最终状态，则需要将所有最终状态转换为非最终状态，并创建一个新的单个最终状态。
示例
步骤 3
DFA 的最终状态没有任何出边。
如果最终状态存在任何出边，则需要创建一个没有出边的新的最终状态。
示例
步骤 4
依次消除所有中间状态。这些状态可以按任何顺序消除
最后，将只剩下一个初始状态到最终状态。
此转换的成本是所需的正则表达式。
2K+ 次查看
