如何将左线性语法转换为右线性语法？

正规语法描述了正规语言。它由以下四个部分组成-

G = (N, E, P, S)

其中，

• 非终结符的有限集合：N,

• 终结符的有限集合：E,

• 一组产生规则，每一个形式如下

• S → aB

• S → a

• S → ∈,

• S ∈ N 是开始符号。

上述语法可以有两种形式-

• 右线性正规语法

• 左线性正规语法

现在，让我们看看将左线性语法转换为右线性语法的步骤-

示例 1

考虑如下给出的左线性语法-

S→ Sa|Abc
A→ Sa|Ab|a

步骤 1 - 我们将给定的左线性语法转换为有限自动机。

步骤 2 - 我们现在将初始状态和最终状态互换。

步骤 3 - 现在，我们将改变所有交易的方向。

步骤 4 - 我们将为上述有限自动机构造正规语法，它将是右线性语法，如下所示-

C→aA
A→bA|cb
S→aS

示例 2

考虑另一个示例

给定的左线性语法为-

S→S10|S11|B|e
B→B0|0

首先消除语法的非确定性

S→SA|B|e
A→10|11
B→B0|0

因此，右线性语法为-

S→BS’|S’
S’→e|10S’|11S’
B→0B’
B’→0B’|e

巴努·普里亚

更新于： 2021 年 6 月 14 日

9K+ 次浏览

启动你的 事业

完成课程，获得认证

开始学习