如何将有限自动机 (FA) 转换为右线性正则文法？

最多只有一个变量出现在产生式右边的文法称为线性文法。

示例 1

      S→aSb/ε

示例 2

      S→Ab

      A→aAb

      A→ε

右线性文法

右线性文法是指所有非终结符都在右端出现的文法。

例如：

      S->aS/ε

转换算法

将有限自动机 (FA) 转换为右线性文法的算法如下：

步骤 1 - 从起始状态开始。

步骤 2 - 对每个状态重复此过程。

步骤 3 - 将产生式作为输出，后跟转换所到达的状态。

步骤 4 - 最后，添加 € (epsilon) 来结束推导。

示例 1

让我们考虑如下所示的有限自动机 (FA)：

选择起始状态 A，在符号 'a' 上的输出到达状态 B

      A→aB

现在我们将选择状态 B，然后我们将继续每个输出

      即 B→aB

      B→bB

      B→ε

因此，

最终的右线性文法如下：

      A→aB

      B→aB/bB/ε

示例 2

从状态 A 开始，它是初始状态，在符号 'a' 上的输出到达 A 和 B，在符号 'b' 上的输出到达 A。现在右线性文法的产生式规则是：

      A→aA/bA/aB

现在选择状态 B，然后继续每个输出，右线性文法是：

      B→aB/bB/ε

给定有限自动机的最终右线性文法是：

      A→aA/bA/aB

      B→aB/bB/ε

更新于：2021年6月12日

6K+ 次浏览

启动你的职业生涯

完成课程获得认证

开始
广告