上下文有关语法的规则可以把上下文aAβ中的非终极符号A重写为任意非空符号串。规则可以写为aAβ→ ayß的形式,或者A→y/a__β的形式。后一种形式在Chomsky-Halle的音位规则表达式中曾经介绍过（Chomsky and Halle,1968）,颤音化（flapping）的规则表示如下：

/t/→[dx]/V__V

这些规则的形式看起来都像上下文有关的。没有递归的音位规则系统的能力实际等价于正则语法。上下文有关的语言模型是树邻接语法（Joshi,1985）。理解上下文有关语法中的规则的另一个办法是：把这种规则想像成以“非递减”的方式把符号串δ重写为符号串Φ，使得Φ中的符号至少与δ中的符号一样多。

上下文无关规则可以把任何一个单独的非终极符号重写为由终极符号和非终极符号构成的符号串。这个单独的非终极符号也可以重写为ε。正则语法与正则表达式等价。也就是说，一个给定的正则语言可以用正则表达式来刻画，也可以用正则语法来刻画。正则语法可以是右线性的（right-linear）,也可以是左线性的（left-linear）。右线性语法规则的右边只有一个单独的非终极符号，左边最多只有一个非终极符号。如果在右边只有一个非终极符号，它必定是符号串中的最后一个符号。左线性语法的右边是可逆的（右边必须至少以一个单独的非终极符号开始）。所有的正则语言既有左线性语法，也有右线性语法。在下面的讨论中，我们只考虑右线性语法。

例如，我们来研究下面的正则（右线性）语法：

S → aA

S → bB

A → aS

B → bbS

S→ε

这是一个正则语法，因为每个规则的左边是一个单独的非终极符号，每个规则的右边至多只有一个（最右边的）非终极符号。下面是这种语言中一个推导的样本：

S⇒ aA ⇒ aaS ⇒ aabB⇒ aabbbS ⇒aabbbaA⇒ aabbbaaS ⇒ aabbbaa

我们可以看出，每次展开S时，它或者产生aaS，或者产生bbbS，因此读者可以相信，这个语言对应于正则表达式（aa U bbb）*。

我们在这里没有证明：一个语言是正则的，当且仅当它是由一个正则语法生成的。这样的证明是首先由Chomsky and Miller(1958)给出的,可以在Hopcroft and Ullman(1979)和Lewis andPapadimitriou(1981)中找到。我们从直觉上可以感到，由于非终极符号总是处于一个规则的最右边或者最左边，它们可以迭代地进行处理，而不可以递归地进行处理。

责任编辑：admin