如何将右线性文法转换为左线性文法？
对于每个有限自动机(FA)，都存在一个正则文法，每个正则文法都有一个左线性和右线性正则文法。
示例1
考虑常规语法-
a(a+b)* A → aB B → aB|bB|e
对于给定的正则表达式，上述文法是右线性文法。
现在，将上面的右线性文法转换为左线性文法。
转换遵循的规则是，
有限自动机→右线性
右线性→左线性文法的逆序。
所以，
A → BaB → Ba|Bb|e
最后对于每一个正确的线性都有一个
示例
考虑一种语言{bnabma|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