4.2.1. 正则文法
正则文法是描述正则语言的另一种方式。回想一下，文法由终结符（terminal）、变量（variable）和产生式规则（production rules）组成。正如名称所示， 正则 文法是一种特殊类型的文法（稍后我们会看到很多不是正则的文法）。这就引出了一个问题：什么使一个文法是正则的？在我们能恰当地回答这个问题之前，需要一些定义。
假设我们有如下文法 \(G = (V, T, S, P)\) ，其中，
\[\begin{split}\begin{array}{lll}
& & \mbox{represented by} \\
V & \mbox{variables (nonterminals)} & A,B,..,Z (that is, capital letters)\\
T & \mbox{terminals} & a,b,..,z,0,1,...9 (lower case letters and numbers)\\
S & \mbox{start symbol} \\
P & \mbox{productions (rules)}\\
\end{array}\end{split}\]
\(V\) 、\(T\) 和 \(P\) 都是有限集合。
线性文法
\[\begin{split}\begin{array}{c}
\mbox{All productions are of the form} \\
A \rightarrow xB \\
A \rightarrow Cx \\
A \rightarrow x \\
\mbox{where}\ A,B,C \in V, x \in T^*
\end{array}\end{split}\]
在这个文法中，每条产生式规则右侧至多有一个变量。（注意：每条产生式中的终结符 \(x\) 不必相同！）
右线性文法
\[\begin{split}\begin{array}{c}
A \rightarrow xB \\
A \rightarrow xC \\
A \rightarrow y \\
\mbox{where}\ A,B,C \in V, x,y \in T^*
\end{array}\end{split}\]
注意：\(x\) 或 \(y\) 是长度为 0 或更长的字符串。每条产生式至多有一个变量，所以该文法是线性的。变量（B 和 C）位于 RHS 的末端，所以它是右线性文法。
左线性文法 右线性文法
\[\begin{split}\begin{array}{c}
A \rightarrow Bx \\
A \rightarrow Cy \\
A \rightarrow x \\
\mbox{where}\ A,B,C \in V, x,y \in T^*
\end{array}\end{split}\]
每条产生式至多有一个变量，所以该文法是线性的。变量（B 和 C）位于 RHS 的开头，所以它是左线性文法。
好了，现在我们有了定义正则文法所需的定义。
定义：
正则文法
Example 4.2.1
\[\begin{split}\begin{eqnarray*}
G &=& (\{S\},\{a,b\},S,P),\\
P &=& \\
&&S \rightarrow abS \\
&&S \rightarrow \lambda \\
&&S \rightarrow Sab \\
\end{eqnarray*}\end{split}\]
该语言是 \((ab)*\) 。
但是，不能混合使用左（left）线性/右（right）线性规则！所以这不是一个正则文法。
Example 4.2.2
\[\begin{split}\begin{eqnarray*}
G &=& (\{S\},\{a,b\},S,P),\\
P &=& \\
&&S \rightarrow aB | bS | \lambda \\
&&B \rightarrow aS | bB \\
\end{eqnarray*}\end{split}\]
这是一个右线性文法，表示语言 \(L = \{ \mbox{strings with an even number of a's}\}, \Sigma = \{a,b\}\)
4.2.1.1. 我们的下一步
我们已经完成的：
定义：DFA 表示正则语言
定理：NFA \(\Longleftrightarrow\) DFA
定理：RE \(\Longleftrightarrow\) NFA
我们接下来要做的：
定理：DFA \(\Longleftrightarrow\) 正则文法
4.2.1.2. 由正则文法构造 NFA
定理： L 是正则语言，当且仅当存在一个正则文法 \(G\) ，使得 \(L = L(G)\) 。
（这里针对右（right）线性文法来做）
(\(\Longleftarrow\) ) 给定正则文法 G，构造 NFA M，使得
\(L(G)=L(M)\) 。
为每个非终结符建立一个状态。
为那条产生式规则中的每个终结符建立转移。
如果存在不含非终结符的产生式，则使其成为终止状态。
对于含多个终结符的规则，需要中间状态。
Example 4.2.3
\(S \rightarrow aB | bS | \lambda\)
\(B \rightarrow aS | bB\)
这是一个右线性文法，表示语言
\(L = \{\) 含偶数个 a 的字符串 \(\}, \Sigma = \{a,b\}\)
那么像 \(S \rightarrow abB\) 这样的规则呢？建立两个状态（在读 a 时从 S 转到中间状态，然后在读 b 时从中间状态转到 B）。
或者 \(S \rightarrow ab\) ？建立两个状态（在读 a 时从 S 转到中间状态，然后在读 b 时从中间状态转移到接受状态）。
4.2.1.3. 由 DFA 构造右线性正则文法
定理： L 是正则语言，当且仅当存在正则文法 G，使得 \(L = L(G)\) 。
(\(\Longrightarrow\) ) 给定 DFA \(M\) ，构造正则文法 \(G\) ，使得 \(L(G)=L(M)\)
这个过程与我们当初从右线性文法构造出 NFA 时基本相同：
每个 DFA 状态对应一个非终结符。
每条转移对应一条产生式规则。
为 NFA 构造正则文法
\(G = (\{S,B\},\{a,b\},S,P)\) ,
\(P =\)
\(Q0 \rightarrow a Q1\)
\(Q1 \rightarrow a Q0 | b Q1 | \lambda\)
4.2.1.4. 值得思考的问题
Example 4.2.4
\(L = \{a^nb^n \mid n>0\}\)
语言 \(L\) 是正则的吗？你能为这种语言画出 DFA、正则表达式或正则文法吗？
考虑这个文法：
\(S \rightarrow aSb \mid ab\)
很好很简单……但这个文法不是正则的！
我们稍后会回到这个问题。
