0

如何将常规语法转换为有限自动机（FA）？例如，对应于以下常规语法的有限自动机会是什么样子？

VN = {S, B, D} (nonterminals)
VT = {a, b, c} (terminals)
 P = {S -> aB, S -> bB, B -> bD, D -> b, D -> aD, B -> cB, B -> aS} (productions)
4

1 回答 1

1

好消息是这并不难。这个想法是每个非终结符都将成为接受语法语言的非确定性有限自动机中的状态，并且产生式将成为转换。我们的 NFA 将具有状态 S、B 和 D，并将根据生产规则在这些状态之间转换。我们的 NFA 如下所示：

       ___a__      _a_
      /      \    /   \
      |      |    \   /
      V      |     \ /
----->S-a,b->B--b-->D
            / \
           /   \
           \_c_/

有一个悬空的生产D -> b我们还没有添加。我们需要引入另一个不对应于非终结符号的状态，以允许我们从 D 转换到 b 并接受一些字符串：

       ___a__      _a_
      /      \    /   \
      |      |    \   /
      V      |     \ /
----->S-a,b->B--b-->D--b-->Q
            / \
           /   \
           \_c_/

现在，如果我们让 S 成为初始状态，Q 成为接受状态，我们就有了一个可以工作的 NFA。如果我们想要一个 DFA，我们可能会注意到这个 FA 只是不确定的，因为我们缺少来自状态 S、D 和 Q 的所需转换。我们可以通过引入一个新的死状态 X 来添加缺失的转换，它将跟踪我们的 NFA刚刚导出在其处理过程中的某个时间点崩溃：

       ___a__      _a_
      /      \    /   \
      |      |    \   /
      V      |     \ /
----->S-a,b->B--b-->D--b-->Q
      |     / \     |      |
      |    /   \    |      |    a,b,c
      c    \_c_/    c    a,b,c  /   \
      |             |      |    \   /
      V             V      V     \ /
      +-------------+------+----->X
于 2020-02-11T14:08:36.280 回答