微客导航 » 文章资讯 » 解释 TOC 中的右线性正则文法

解释 TOC 中的右线性正则文法

2023-06-07 16:37:03 448

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

G = (N, E, P, S)

在哪里，

N-非终结符的有限集，

E-一个有限的终端符号集，

P-一组产生式规则，每一个都在形式中

S→aB

S→一个

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={bⁿab^ma|n>=2，m>=2}

给定语言的产生式规则或语法L={bⁿab^ma|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