解释有限自动机和正则表达式之间的关系。

为了理解有限自动机 (FA) 和正则表达式 (RE) 之间的关系，我们需要理解这些术语。让我们从了解什么是正则表达式开始。

正则表达式

正则表达式是一种用于描述语言并被有限自动机接受的语言。正则表达式是表示任何语言的最有效方法。令 Σ 为表示输入集的字母表。

Σ 上的正则表达式可以定义如下：

  • Φ 是一个正则表达式，表示空集。
  • ε 是一个正则表达式，表示集合 {ε}，称为空字符串。
  • 对于 Σ 中的每个 'a'，'a' 是一个正则表达式，表示集合 {a}。
  • 如果 r 和 s 是表示语言的正则表达式。
    • 分别为 L1 和 L2，则：
    • r+s 等价于 L1 U L2 并集
    • rs 等价于 L1L2 连接
    • r* 等价于 L1* 闭包

r* 被称为 Kleen 闭包或闭包，表示 r 的无限次出现。

现在，让我们了解有限自动机。

有限自动机

有限自动机是一种抽象的计算设备。它是具有离散输入、输出、状态和一组状态转换的系统的数学模型，这些转换在来自字母表 Σ 的输入符号上发生。

有限自动机的形式化定义

有限自动机定义为一个 5 元组

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

其中：

  • Q：称为状态的有限集。
  • Σ：称为字母表的有限集。
  • δ：Q × Σ → Q 是转换函数。
  • q0 ∈ Q 是起始或初始状态。
  • F：最终或接受状态。

现在我们已经了解了这些术语，让我们了解它们之间的关系。

关系

FA 和 RE 之间的关系如下：

上图说明了将

  • RE 转换为带有 epsilon 移动的非确定性有限自动机 (NFA) 很容易。
  • 带有 epsilon 移动的 NFA 转换为不带 epsilon 移动的 NFA。
  • 不带 epsilon 移动的 NFA 转换为确定性有限自动机 (DFA)。
  • DFA 可以很容易地转换为 RE。

更新于：2021 年 6 月 12 日

11K+ 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告