1

顾名思义，DFA 和 NFA 与正则表达式有什么关系？学习 DFA 和 NFA 是否有助于更好地理解正则表达式？

4

2 回答 2

3

有限自动机（fa）、正则表达式（re）以及正则文法，都是正则语言的有限表示。它们的目的都是表达一种常规的集合/语言（对于其他类语言，如 cfg、csl 等也是如此）。

自动机对于理论目的相对更有用，用于分析语言属性 - 复杂性类别。

在有限自动机的情况下，确定性 (DFA)和非确定性 (NFA)模型都表示同一类语言，称为“常规语言”（对于 npda ≭ pda 的其他语言而言并非如此）。

正则表达式（re）：是另一种以字母形式表示正则语言的方法，这对于表示编程语言中的一组有效字符串非常有帮助（这里自动机不能直接有用，而正则表达式对分析没有多大帮助语言属性，例如完全描述抽水引理）。

DFA 和 NFA 与正则表达式有何关系？

  • 两者都代表同一类语言——常规语言

  • 不可能直接从语言的英文描述中通过算法构造自动机或正则表达式。虽然，如果我们有任何一种表示（FA 或 RE），那么我们可以系统地编写其他表示，例如。我们可以使用 Arden 定理逐步系统地为 DFA/NFA 编写正则表达式。 （检查此链接）

    让我们举一个语言示例：L =“偶数个a's 和b's”。

    L 的正则表达式为：

    (
 (a + b(aa)*ab)(bb)*(ba(aa)*ab(bb)*)*a +
 (b + a(bb)*ba)(aa)*(ab(bb)*ba(aa)*)*b
)*

    直接为这种语言编写正则表达式非常困难（即使是快速理解这一点也很典型）。

    但是从 DFA 并使用 Arden't 定理，为语言 L 编写正则表达式很简单。

    重要的是，为这种语言绘制 DFA 相对简单（也容易记忆）。

    另一个例子可以是“符号0和1，其中二进制字符串的十进制等价物可以被 5 整除”的语言，为此编写 RE 与编写 DFA 相比非常困难。

  • 我们还可以通过算法从常规语言中提取 DFA 。

学习 DFA 和 NFA 是否有助于更好地理解正则表达式？

是的，因为以下原因：

  • 有时很难直接编写 RE。

  • 直接从英文描述中编写的正则表达式可能有问题。错误 dfa 的机会将小于错误正则表达式，这就是为什么当我们为某些语言编写编译器时，优先/正确的步骤被认为是首先从每个标记中提取 DFA，然后编写它们的等价正则表达式 - DFA 将被视为正确性的证明 - dfa更具描述性和易于掌握的语言结构（DFA 是正确的，然后 RE 是正确的）。

  • 如果re很复杂，你要找到“语言描述是什么？”，那么你可以从re中提取DFA，然后给出语言描述。

  • 有时要找到更好的 re，您可以绘制 DFA，然后将其转换为最小化 DFA，然后使用最小化的 DFA 编写 re，可能会给您更好的解决方案。（它不是通用技术，有时可能会有所帮助）

  • 如果很难比较两个正则表达式，那么您可以比较它们对应的 DFA 以检查等价性。

注意：有时编写正则表达式比绘制 DFA 简单得多。

于 2013-07-07T13:48:14.777 回答
0

非确定性有限自动机 (NFA)是一种可以识别常规语言的机器。

正则表达式是描述正则语言的字符串。

可以通过算法构建一个能够识别给定正则表达式描述的语言的 NFA。在输入字符串上运行 NFA 将告诉您正则表达式是否与输入字符串匹配。

因此，NFA 可用于实现正则表达式引擎，但不需要了解它们即可充分发挥正则表达式的潜力。

于 2013-07-07T07:36:26.917 回答