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

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

示例 1

考虑常规语法 -

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

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

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

转换遵循的规则是，

有限自动机 → 右线性

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

所以，

A → BaB → Ba|Bb|e

最后对于每一个正确的线性都有一个

示例

考虑一种语言 {b ⁿ ab ^m a| 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