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

对于每个有限状态自动机 (FA)，都存在一个正则文法，而对于每个正则文法，都存在一个左线性和右线性正则文法。

示例 1

考虑一个正则语法 -

   a(a+b)*
A → aB
B → aB|bB|e

对于给定的正则表达式，上述文法是右线性文法。

现在，将上述右线性文法转换为左线性文法。

转换遵循的规则是，

有限状态自动机 → 右线性

右线性的反转 → 左线性文法。

所以，

A → Ba
B → Ba|Bb|e

最后对于每个右线性都有一个

示例

考虑一个语言 {bⁿab^ma| n>=2, m>=2}

给定语言的右线性文法是 -

bn ⇒ A→bA|b       A is on right side
bm ⇒ B→bB|b       B is on right side

完整的表达式文法是 -

S→AaBa
A→bA|b
B→bB|b.

上述右线性文法的左文法是，

bn ⇒ A→Ab|b
bm ⇒ B→Bb|b

完整的表达式文法如下 -

S→AaBa
A→Ab|b
B→Bb|b

巴努·普里亚

更新日期： 14-6 月-2021

5K+ 浏览

启动 职业生涯

通过完成课程获取认证

入门