正則文法的限制是什麼？

正則文法是指每個產生式都採用以下受限形式之一的文法：

B → ∧, B → w,

B → A,

B → wA.

（其中A，B是非終結符，w是非空終結符串。）

正則文法的限制

• 產生式的右側只能出現一個非終結符。

• 非終結符必須出現在右側的末尾。

因此，產生式如下所示：

A → aBc 和 S → TU

這些不是正則文法的一部分，但產生式A → abcA 是。

像 A → aB|cC 這樣的形式是允許的，因為它們實際上是兩個獨立的產生式。

對於任何正則語言，我們都可以找到一個能夠產生它的正則文法。

但是，也可能存在其他非正則文法也能產生它。

示例

對於正則語言a*b*

示例

為正則表示式a*bc*的語言構造一個正則文法。

首先，a*bc* 的字串以a或b開頭。

S → aS | bC.

我們可以推匯出bC、abC、aabC等形式的字串。

現在我們需要C的定義來推匯出c*的語言：

C → ∧ | cC.

因此，a*bc* 的正則文法可以寫成：

S → aS | bC; C → ∧ | cC.

Bhanu Priya

更新於：2021年6月15日

810 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習