微客导航 » 文章资讯 » 如何将右线性文法转换为左线性文法？

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

2023-06-07 16:35:03 440

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

示例1

考虑常规语法-

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

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

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

转换遵循的规则是，

有限自动机→右线性

右线性→左线性文法的逆序。

所以，

A → BaB → 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