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

/t/→[dx]/V__V

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

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

例如，我們來研究下面的正則（右線性）語法：

S → aA

S → bB

A → aS

B → bbS

S→ε

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

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

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

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

責(zé)任編輯：admin