正则文法描述了正则语言。它由四个部分组成，如下所示 -
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 n ab m a | n>=2，m>=2}
给定语言的产生式规则或语法 L= {b n ab m a | 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