在目錄中解釋左線性正規文法

正規文法描述正規語言。它由四個組成部分組成，如下所示：

G = (N, E, P, S)

其中：

• N - 非終結符的有限集合；

• E - 終結符的有限集合；

• P - 產生式規則的集合，每個規則都採用以下形式：

• S → aB

• S → a

• S → ∈,

• S ∈ N 是起始符號。

上述文法可以有兩種形式：

• 右線性正規文法

• 左線性正規文法

線性文法

當文法部分的右側只有一個終結符時，它是線性的，否則是非線性的。

左線性文法

在左正規文法（也稱為左線性文法）中，規則的形式如下所示：

• L → a, {L是N中的非終結符，a是Σ中的終結符}

• L → Ma, {L和M都在N中，a在Σ中}

• L → ∈, {∈是空字串}。

左線性文法意味著非終結符將位於左側。

示例

考慮語言{bⁿab^ma| n>=2, m>=2}

基於給定語言生成的左線性文法是：

S → Bbba       ⇒ last 3 symbols bba
B → Bb| Dbba   ⇒ for bm and bba are for bn followed by a.
D → Db|e       ⇒ for bn-2

Bhanu Priya

更新於：2021年6月14日

4K+ 瀏覽量

啟動你的職業生涯

透過完成課程獲得認證

開始學習