在 TOC 中解释右线性正规文法

正规文法描述正规语言。它包含四个构成部分，如下所述 −

G = (N, E, P, S)

其中，

  • N − 非终结符号的有限集合，

  • E − 终结符号的有限集合，

  • P − 一组产生式，每条产生式均采用以下形式

  • S → aB

  • S → a

  • S → ∈，

  • S ∈ N 是起始符号。

以上文法可以有两种形式 −

  • 右线性正规文法

  • 左线性正规文法

线性文法

如果文法部分的右侧只含有一个终结符，那么它是线性的，否则是非线性的。

我们来讨论一下右线性文法 −

右线性文法

右线性文法表示非终结符号将位于产生式的右侧。

它是由形式文法 (N, Σ, P, S) 组成，其中 P 中的所有产生式均采用如下形式之一 −

L → a, { L is a non-terminal and a is a terminal in Σ}
L → aM, {L and M are non-terminals in N and a is in Σ}
L → ∈.

示例

考虑语言 L= {bnabma | n>=2, m>=2}

给定语言 L= {bnabma | n>=2, m>=2} 的产生式或文法是 −

S→bbB    ⇒for first 2 b’s
B→bB|aC  ⇒ any number of b’s followed by a
C→bbD    ⇒ 2b’s
D→ bD|a  ⇒ any number of b’s followed by a

更新于: 14-6 月 - 2021

3K+ 浏览量

开始你的 职业生涯

通过完成课程获得认证

开始
广告