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

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

示例 1

考虑常规语法 -

   a(a+b)*

A → aB

B → aB|bB|e

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

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

转换遵循的规则是,

有限自动机 → 右线性

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

所以,

A → BaB → Ba|Bb|e

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

示例

考虑一种语言 {b n 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

以上是 如何将右线性文法转换为左线性文法? 的全部内容, 来源链接: utcz.com/z/354422.html

回到顶部