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

正規語法描述了正規語言。它由以下四個部分組成-

G = (N, E, P, S)

其中，

• 非終結符的有限集合：N,

• 終結符的有限集合：E,

• 一組產生規則，每一個形式如下

• S → aB

• S → a

• S → ∈,

• S ∈ N 是開始符號。

上述語法可以有兩種形式-

• 右線性正規語法

• 左線性正規語法

現在，讓我們看看將左線性語法轉換為右線性語法的步驟-

示例 1

考慮如下給出的左線性語法-

S→ Sa|Abc
A→ Sa|Ab|a

步驟 1 - 我們將給定的左線性語法轉換為有限自動機。

步驟 2 - 我們現在將初始狀態和最終狀態互換。

步驟 3 - 現在，我們將改變所有交易的方向。

步驟 4 - 我們將為上述有限自動機構造正規語法，它將是右線性語法，如下所示-

C→aA
A→bA|cb
S→aS

示例 2

考慮另一個示例

給定的左線性語法為-

S→S10|S11|B|e
B→B0|0

首先消除語法的非確定性

S→SA|B|e
A→10|11
B→B0|0

因此，右線性語法為-

S→BS’|S’
S’→e|10S’|11S’
B→0B’
B’→0B’|e

巴努·普里亞

更新於： 2021 年 6 月 14 日

9K+ 次瀏覽

啟動你的 事業

完成課程，獲得認證

開始學習