解释 TOC 中的右线性正则文法
正则文法描述了正则语言。它由四个部分组成,如下所示-
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={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