如何將右線性文法轉換為左線性文法？

對於每個有限狀態自動機 (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+ 瀏覽

啟動 職業生涯

透過完成課程獲取認證

入門