上下文有關(guān)語(yǔ)法的規(guī)則可以把上下文aAβ中的非終極符號(hào)A重寫(xiě)為任意非空符號(hào)串。規(guī)則可以寫(xiě)為aAβ→ ay?的形式,或者A→y/a__β的形式。后一種形式在Chomsky-Halle的音位規(guī)則表達(dá)式中曾經(jīng)介紹過(guò)（Chomsky and Halle,1968）,顫音化（flapping）的規(guī)則表示如下：

/t/→[dx]/V__V

這些規(guī)則的形式看起來(lái)都像上下文有關(guān)的。沒(méi)有遞歸的音位規(guī)則系統(tǒng)的能力實(shí)際等價(jià)于正則語(yǔ)法。上下文有關(guān)的語(yǔ)言模型是樹(shù)鄰接語(yǔ)法（Joshi,1985）。理解上下文有關(guān)語(yǔ)法中的規(guī)則的另一個(gè)辦法是：把這種規(guī)則想像成以“非遞減”的方式把符號(hào)串δ重寫(xiě)為符號(hào)串Φ，使得Φ中的符號(hào)至少與δ中的符號(hào)一樣多。

上下文無(wú)關(guān)規(guī)則可以把任何一個(gè)單獨(dú)的非終極符號(hào)重寫(xiě)為由終極符號(hào)和非終極符號(hào)構(gòu)成的符號(hào)串。這個(gè)單獨(dú)的非終極符號(hào)也可以重寫(xiě)為ε。正則語(yǔ)法與正則表達(dá)式等價(jià)。也就是說(shuō)，一個(gè)給定的正則語(yǔ)言可以用正則表達(dá)式來(lái)刻畫(huà)，也可以用正則語(yǔ)法來(lái)刻畫(huà)。正則語(yǔ)法可以是右線性的（right-linear）,也可以是左線性的（left-linear）。右線性語(yǔ)法規(guī)則的右邊只有一個(gè)單獨(dú)的非終極符號(hào)，左邊最多只有一個(gè)非終極符號(hào)。如果在右邊只有一個(gè)非終極符號(hào)，它必定是符號(hào)串中的最后一個(gè)符號(hào)。左線性語(yǔ)法的右邊是可逆的（右邊必須至少以一個(gè)單獨(dú)的非終極符號(hào)開(kāi)始）。所有的正則語(yǔ)言既有左線性語(yǔ)法，也有右線性語(yǔ)法。在下面的討論中，我們只考慮右線性語(yǔ)法。

例如，我們來(lái)研究下面的正則（右線性）語(yǔ)法：

S → aA

S → bB

A → aS

B → bbS

S→ε

這是一個(gè)正則語(yǔ)法，因?yàn)槊總€(gè)規(guī)則的左邊是一個(gè)單獨(dú)的非終極符號(hào)，每個(gè)規(guī)則的右邊至多只有一個(gè)（最右邊的）非終極符號(hào)。下面是這種語(yǔ)言中一個(gè)推導(dǎo)的樣本：

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

我們可以看出，每次展開(kāi)S時(shí)，它或者產(chǎn)生aaS，或者產(chǎn)生bbbS，因此讀者可以相信，這個(gè)語(yǔ)言對(duì)應(yīng)于正則表達(dá)式（aa U bbb）*。

我們?cè)谶@里沒(méi)有證明：一個(gè)語(yǔ)言是正則的，當(dāng)且僅當(dāng)它是由一個(gè)正則語(yǔ)法生成的。這樣的證明是首先由Chomsky and Miller(1958)給出的,可以在Hopcroft and Ullman(1979)和Lewis andPapadimitriou(1981)中找到。我們從直覺(jué)上可以感到，由于非終極符號(hào)總是處于一個(gè)規(guī)則的最右邊或者最左邊，它們可以迭代地進(jìn)行處理，而不可以遞歸地進(jìn)行處理。

責(zé)任編輯：admin