正则文法的限制是什么？

正则文法是指每个产生式都采用以下受限形式之一的文法：

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.

更新于：2021年6月15日

810 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告