在目录中解释左线性正规文法

正规文法描述正规语言。它由四个组成部分组成，如下所示：

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 → ∈, {∈是空字符串}。

左线性文法意味着非终结符将位于左侧。

示例

考虑语言{bnabma| 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

更新于：2021年6月14日

4K+ 浏览量

启动你的职业生涯

通过完成课程获得认证

开始学习
广告