計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)

計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)第一頁，共三十七頁，編輯于2023年，星期五1.1符號(hào)、符號(hào)串及其運(yùn)算字母表：一個(gè)非空的有限集合稱為字母表，通常用或者大寫的西文字母表示。字母表中的元素稱作為字母或符號(hào)，一般用小寫字母、數(shù)字等表示。符號(hào)串：一個(gè)符號(hào)串是由字母表中的字母組成的一個(gè)有限序列。符號(hào)串的長(zhǎng)度：符號(hào)串所包含符號(hào)的個(gè)數(shù)稱為符號(hào)串的長(zhǎng)度。符號(hào)串w的長(zhǎng)度記為|w|?？沾洪L(zhǎng)度為0的符號(hào)串稱為空串，用表示。王雷@版權(quán)所有第二頁，共三十七頁，編輯于2023年，星期五1.1符號(hào)、符號(hào)串及其運(yùn)算符號(hào)串的聯(lián)結(jié)：聯(lián)結(jié)是符號(hào)串的基本運(yùn)算。兩個(gè)符號(hào)串X和Y的聯(lián)結(jié)，記為XY，就是把Y跟隨在X的后面形成的符號(hào)串。例1.1：設(shè)

={1,2}是一個(gè)字母表。設(shè)X=11、Y=22分別是上的兩個(gè)符號(hào)串。則：

XY=1122是X、Y兩個(gè)符號(hào)串的聯(lián)結(jié)，XY是上的一符號(hào)串。YX=2211是Y、X兩個(gè)符號(hào)串的聯(lián)結(jié)，YX也是上的一符號(hào)串。一般來說，符號(hào)串的聯(lián)結(jié)不滿足交換律。顯然符號(hào)串的聯(lián)結(jié)是滿足結(jié)合律的，即有，(XY)Z=X(YZ)。在例1.1中，顯然有XY≠YX，(XY)X=X(YX)=112211。王雷@版權(quán)所有第三頁，共三十七頁，編輯于2023年，星期五1.1符號(hào)、符號(hào)串及其運(yùn)算由于是不含符號(hào)的符號(hào)串(空串)，所以對(duì)任意符號(hào)串X都有，X=X=X。由此我們可以認(rèn)為是符號(hào)串聯(lián)結(jié)運(yùn)算的單位元。符號(hào)串的方冪：設(shè)X是符號(hào)串，把X自身聯(lián)結(jié)n次后，得到的符號(hào)串Z，即Z=XX…XX=Xn，稱為X的方冪。我們約定X0=。這個(gè)定義可以遞歸地表示為：AB王雷@版權(quán)所有第四頁，共三十七頁，編輯于2023年，星期五1.1符號(hào)、符號(hào)串及其運(yùn)算符號(hào)串的子串、前綴和后綴：符號(hào)串V是符號(hào)串W的子串，當(dāng)且僅當(dāng)存在符號(hào)串X和Y，使得W=XVY。這里，X和Y都可能是空串。集合的聯(lián)結(jié)：設(shè)A和B都是符號(hào)串的集合，定以集合A和B的聯(lián)結(jié)為：AB={XY|X∈A且Y∈B}，即集合A和B的聯(lián)結(jié)是集合A中的符號(hào)串和集合B中的符號(hào)串的聯(lián)結(jié)所構(gòu)成的集合。

AB王雷@版權(quán)所有第五頁，共三十七頁，編輯于2023年，星期五1.1符號(hào)、符號(hào)串及其運(yùn)算集合的方冪：設(shè)A是符號(hào)串的集合，把A自身聯(lián)結(jié)n次后，得到的新的集合An，即An=A…A…A，稱為集合A的方冪。我們約定A0={}。這個(gè)定義可以遞歸地表示為：王雷@版權(quán)所有第六頁，共三十七頁，編輯于2023年，星期五1.1符號(hào)、符號(hào)串及其運(yùn)算集合的閉包和正閉包：設(shè)A是符號(hào)串的集合，用A*表示A的所有的有限次方冪的并集，則稱A*為集合A上的閉包，即：注意：閉包A*與正閉包A+的差別在于是否包含空串。在閉包A*中去掉空串后就成為正閉包A+。A*具有可數(shù)無窮多的符號(hào)串。A*=A0∪A1∪A2∪…∪An∪…而稱A+=A1∪A2∪…∪An∪…為A上的正閉包，顯然,有A*=A0∪A+

，A+=A*A=AA*。語言：令為一個(gè)字母表。若L

*，則L是字母表上的一個(gè)語言。即：L為一個(gè)由字母表上的字符串所構(gòu)成的集合。王雷@版權(quán)所有第七頁，共三十七頁，編輯于2023年，星期五1.2文法與語言的形式定義語言都是用文法來描述的。一個(gè)文法實(shí)際上是一組有限的規(guī)則式。非終結(jié)符（一種過渡性符號(hào)）：也是一種符號(hào)，但不是字母表中的符號(hào)。我們將它記為V。終結(jié)符：是一個(gè)語言的字母表中的符號(hào)。我們將它記為T。對(duì)于一個(gè)形式語言L，設(shè)T和V分別是它的終結(jié)符集和非終結(jié)符集，顯然有LT*，且T∩V=。王雷@版權(quán)所有第八頁，共三十七頁，編輯于2023年，星期五1.2.1文法的形式化定義定義1.1：一條產(chǎn)生式是一個(gè)有序?qū)?,),通?？蓪懽魅缦滦问健?

或其中：∈V+，∈V’*，V’=V∪T。稱為產(chǎn)生式的左部，稱為產(chǎn)生式的右部。注意：∈V+說明是一個(gè)非終結(jié)符且≠，即產(chǎn)生式的左部不允許是空串。∈V’*說明產(chǎn)生式的右部是這樣的一個(gè)符號(hào)串，它可以含有終結(jié)符，也可以含有非終結(jié)符，同時(shí)還可以為空串。王雷@版權(quán)所有第九頁，共三十七頁，編輯于2023年，星期五1.2.1文法的形式化定義定義1.2：文法G定義為一個(gè)四元組G=(V，T，P，S),其中：1、V是一個(gè)非空的有窮集合，稱為非終結(jié)符集。2、T是一個(gè)非空的有窮集合，稱為終結(jié)符集，且V∩T=。3、P是一個(gè)非空的有窮的產(chǎn)生式的集合。4、S∈V，稱為文法的開始符號(hào)，S至少要在P中的一條產(chǎn)生式中作為左部出現(xiàn)。王雷@版權(quán)所有第十頁，共三十七頁，編輯于2023年，星期五1.2.1文法的形式化定義例1.2設(shè)文法G=({A,E}，{a}，P，A)，其中P={Aa，AaE，EaA}。在許多的文法中，有多條產(chǎn)生式的左部相同，可以將左部相同的產(chǎn)生式寫成合并的產(chǎn)生式形式。在此例文法G中，P中的前兩個(gè)產(chǎn)生式的左部相同，都是A，可以合并為Aa|aE，這樣一來，P={Aa|aE，EaA}。在許多情況下，只需要將文法的產(chǎn)生式寫出就可以表明該文法了。約定：第一條產(chǎn)生式的左部是文法的開始符

王雷@版權(quán)所有第十一頁，共三十七頁，編輯于2023年，星期五1.2.2推導(dǎo)的形式化定義定義1.3：給定一個(gè)文法G=(V,T,P,S)，如果是G中的一條產(chǎn)生式，和是V’*中的任意符號(hào)，若存在符號(hào)串x,y滿足：x=，y=，則稱x使用了產(chǎn)生式直接產(chǎn)生了y，或者稱y是x的直接推導(dǎo)，或者稱y可以直接歸約到x，記作xy。例：令x=aAb，y=acb，

=a，

=b，則y是x的直接推導(dǎo)，即：aAbacb，所使用的產(chǎn)生式為Ac。王雷@版權(quán)所有第十二頁，共三十七頁，編輯于2023年，星期五1.2.2推導(dǎo)的形式化定義定義1.4：給定一個(gè)文法G=(V,T,P,S)，設(shè)x，yV*，如果：

1、存在如下的直接推導(dǎo)序列：x=w0w1w2…wn=y(n＞0)則稱x推導(dǎo)出(產(chǎn)生)y，推導(dǎo)長(zhǎng)度為n，或者稱為y歸約到x，記作xny。

2、我們用x+y表示存在n＞0且xny；用x*y表示有x+

y或者x=y。最左(右)推導(dǎo)：如果在推導(dǎo)的每一步xy，都是對(duì)x中的最左(右)邊的非終結(jié)符選用產(chǎn)生式進(jìn)行替換，則這種推導(dǎo)稱為最左(右)推導(dǎo)。最右推導(dǎo)也稱為規(guī)范推導(dǎo)。王雷@版權(quán)所有第十三頁，共三十七頁，編輯于2023年，星期五1.2.2推導(dǎo)的形式化定義規(guī)范句型、短語、直接短語和句柄定義1.5：給定一個(gè)文法G=(V,T,P,S)，如果符號(hào)串x是從文法G的開始符號(hào)S推導(dǎo)出來的，即S*x，則稱x是文法G的句型。如果符號(hào)串x是僅由終結(jié)符組成的句型，即S*x且x∈T*，則稱x是文法G的句子。由規(guī)范推導(dǎo)所得到的句型就稱之為規(guī)范句型。王雷@版權(quán)所有第十四頁，共三十七頁，編輯于2023年，星期五1.2.2推導(dǎo)的形式化定義規(guī)范句型、短語、直接短語和句柄定義1.6

設(shè)G[S]是一文法，x=w是一句型，如果：S*A且A*

w則稱w是句型x的一個(gè)相對(duì)于非終結(jié)符A的短語；如果：S*A且Aw則稱w是句型x的一個(gè)相對(duì)于非終結(jié)符Ａ的直接短語(或簡(jiǎn)單短語)；如果w是一個(gè)句型x的最左直接短語，稱w為句型x的句柄。王雷@版權(quán)所有第十五頁，共三十七頁，編輯于2023年，星期五1.2.3語言的形式化定義定義1.7：給定一個(gè)文法G=(V,T,P,S)，由G所生成的語言記作L(G)，令L(G)={x|S+x且x∈T*}，其中x稱為語言L(G)的句子。即：L(G)是一個(gè)由從文法G的開始符號(hào)S所推導(dǎo)出來的所有句子所構(gòu)成的集合。例1.3給定文法G[S]：SaSb|ab

由該文法生成的任何一個(gè)句子都是：先使用產(chǎn)生式SaSb若干次得到：SaSbaaSbb…an-1Sbn-1

，即S+an-1Sbn-1

；再使用產(chǎn)生式Sab一次得到：S+an-1Sbn-1

anbn。不難對(duì)推導(dǎo)的步數(shù)用數(shù)學(xué)歸納法證明該文法推導(dǎo)的所有符號(hào)串都是anbn的形式。另一方面，我們也不難對(duì)符號(hào)串的長(zhǎng)度用數(shù)學(xué)歸納法證明，對(duì)任何形式為anbn，n≥1，的符號(hào)串，一定可以用文法G[S]推導(dǎo)出來，即存在推導(dǎo)S+anbn。所以，L(G[S])={anbn|n1}。王雷@版權(quán)所有第十六頁，共三十七頁，編輯于2023年，星期五1.2.3語言的形式化定義例1.4設(shè)文法G[V]：VaVb，VbbW，abWc。求文法G[V]所生成的語言。解：V是文法的開始符。繼續(xù)多次使用該產(chǎn)生式，得到的推導(dǎo)結(jié)果是：anVbn，n≥1。在anVbn中，為了消除非終結(jié)符V，必須使用產(chǎn)生式VbbW，得到推導(dǎo)結(jié)果是：anbWbn-1=an-1abWbn-1，n≥1。只有使用產(chǎn)生式abWc，才能消除非終結(jié)符W，最終得到推導(dǎo)結(jié)果：an-1cbn-1，n≥1。另一方面，不難證明，對(duì)任何形式為ancbn，n≥0的符號(hào)串都可以用文法G[V]推導(dǎo)出來。因此，文法G[V]生成的語言為：L(G[V])={an-1cbn-1|n≥1}={ancbn|n≥0}。王雷@版權(quán)所有第十七頁，共三十七頁，編輯于2023年，星期五1.2.3語言的形式化定義例1.5文法G[A]：AaR，Aab，RAb所生成的語言L(G[A])={anbn|n1}。(留做課后習(xí)題)。從上面可以看出，盡管文法G[A]與例1.7中的文法G[S]是兩個(gè)不同的文法，但是所生成的語言是相同，都是{anbn|n1}。定義1.8

給定任意兩個(gè)文法G1、G2，如果它們所生成語言相同，即：L(G1)=L(G2)，則稱文法G1與G2是等價(jià)的。王雷@版權(quán)所有第十八頁，共三十七頁，編輯于2023年，星期五1.2.4語法樹語法樹是句型推導(dǎo)過程的圖形表示。例如，設(shè)句子bd0的最右推導(dǎo)或規(guī)范推導(dǎo)為：<標(biāo)識(shí)符><標(biāo)識(shí)符><數(shù)字><標(biāo)識(shí)符>0<標(biāo)識(shí)符><字母>0<標(biāo)識(shí)符>d0<字母>d0bd0王雷@版權(quán)所有<標(biāo)識(shí)符><數(shù)字><標(biāo)識(shí)符><標(biāo)識(shí)符><字母><字母>bd0圖1.2句子bd0的語法樹第十九頁，共三十七頁，編輯于2023年，星期五1.2.4語法樹定義1.9如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵以上的不同的語法樹，或有兩個(gè)以上的不同的最左(右)推導(dǎo)，則稱該文法是二義性文法（程序設(shè)計(jì)語言不能有二義性）。定義1.10如果一個(gè)語言L的任何文法都是二義性文法，則稱該語言L是二義性語言。在理論上已經(jīng)證明了，存在著這種二義性的語言。

文法的二義性與語言的二義性是兩個(gè)不同的概念。AB王雷@版權(quán)所有第二十頁，共三十七頁，編輯于2023年，星期五1.2.5文法和語言的類型Chomsky于1956年把文法分成四種類型，即：0型文法、1型文法、2型文法和3型文法。這種文法的分類稱作Chomsky分類。文法所生成的語言，根據(jù)四種類型文法，也分為四種，即：0型語言、1型語言、2型語言和3型語言。Chomsky建立的形式語言理論對(duì)計(jì)算機(jī)科學(xué)的發(fā)展規(guī)律有著深刻的影響，特別是對(duì)計(jì)算機(jī)程序設(shè)計(jì)語言的設(shè)計(jì)、編譯方法和計(jì)算復(fù)雜性等方面具有更大的作用。王雷@版權(quán)所有諾姆·喬姆斯基（NoamChomsky,1928--），美國(guó)語言學(xué)家，轉(zhuǎn)換-生成語法的創(chuàng)始人。1928年12月7日出生于美國(guó)賓夕法尼亞州的費(fèi)城。1947年，在哈里斯的影響下他開始研究語言學(xué)。1951年在賓夕法尼亞大學(xué)完成碩士論文《現(xiàn)代希伯萊語語素音位學(xué)》，1955年在該校完成博士論文《轉(zhuǎn)換分析》，獲得博士學(xué)位。從1955年秋天開始，他一直在麻省理工學(xué)院工作，曾任該校語言學(xué)與哲學(xué)系主任，并任該校認(rèn)知科學(xué)研究中心主任，為語言學(xué)界培養(yǎng)了一批有素養(yǎng)的學(xué)者。第二十一頁，共三十七頁，編輯于2023年，星期五1.2.5文法和語言的類型定義1.11設(shè)文法G=(V,T,P,S)，如果，對(duì)于P，滿足(V∪T)+且中至少含有一個(gè)非終結(jié)符，(V∪T)*，則G稱為0型文法（或短語結(jié)構(gòu)文法，簡(jiǎn)記為PSG)或者無約束文法(UnrestrictedGrammar)。0型文法能確保產(chǎn)生式的左部不為空。由0型文法所生成的語言稱為0型語言或短語結(jié)構(gòu)語言（簡(jiǎn)記為PSL）。0型文法的能力與圖靈機(jī)（TuringMachine）相當(dāng)。王雷@版權(quán)所有第二十二頁，共三十七頁，編輯于2023年，星期五1.2.5文法和語言的類型定義1.12設(shè)文法G=(V,T,P,S)，如果對(duì)于P，滿足||≥||(除S外)，則文法G稱為1型文法或上下文有關(guān)文法，簡(jiǎn)記為CSG。1型文法的產(chǎn)生式的形式也被描述為：1A212，其中：1、2

、(V∪T)+，AV。它更能體現(xiàn)“上下文有關(guān)”這一含義，因?yàn)?，只有A出現(xiàn)在1和2之間（1為A的上文，2為A的下文），才允許用來取代A。1型文法所產(chǎn)生的語言稱作1型語言或上下文有關(guān)語言(簡(jiǎn)記為CSL)。王雷@版權(quán)所有第二十三頁，共三十七頁，編輯于2023年，星期五1.2.5文法和語言的類型定義1.13設(shè)文法G=(V,T,P,S)，如果，對(duì)于P，滿足V，(V∪T)*，則稱G為2型文法或上下文無關(guān)文法，簡(jiǎn)記為CFG。上下文無關(guān)文法取名為“上下文無關(guān)”的原因就是因?yàn)樽址偪梢员蛔执杂商鎿Q，而無需考慮字符出現(xiàn)的上下文。2型文法所產(chǎn)生的語言稱作2型語言或上下文無關(guān)語言(簡(jiǎn)記為CFL)。一個(gè)簡(jiǎn)單的上下文無關(guān)文法的例子是：S->aSb|ε。由于這個(gè)文法的產(chǎn)生式的左邊都是單個(gè)的非終結(jié)符S，右邊是由終結(jié)符或非終結(jié)符構(gòu)成的符號(hào)串a(chǎn)Sb和ε，因此符合上下文無關(guān)語法產(chǎn)生式的要求。該文法產(chǎn)生的語言為{anbn:n≥0}。王雷@版權(quán)所有第二十四頁，共三十七頁，編輯于2023年，星期五1.2.5文法和語言的類型定義1.14：設(shè)文法G=(V,T,P,S)，如果P中的每一條產(chǎn)生式都是AaB或Aa形式，其中：A、BV，aT，則稱G為3型文法或正規(guī)文法,簡(jiǎn)記為RG。3型文法所產(chǎn)生的語言稱作3型語言或正規(guī)語言(簡(jiǎn)記為RL)。3型語言與有限自動(dòng)機(jī)等價(jià)，即有限自動(dòng)機(jī)恰能識(shí)別3型語言。0型語言1型語言2型語言3型語言圖1.4形式語言的Chomsky層級(jí)在忽略句子ε的情況下，由Chomsky分類定義可知，任何3型語言都是2型語言，任何2型語言都是1型語言，任何1型語言都是0型語言。王雷@版權(quán)所有第二十五頁，共三十七頁，編輯于2023年，星期五1.2.5文法和語言的類型王雷@版權(quán)所有0型語言1型語言2型語言3型語言圖1.4形式語言的Chomsky層級(jí)第二十六頁，共三十七頁，編輯于2023年，星期五1.3正規(guī)表達(dá)式（正規(guī)式

）正規(guī)式是按照一組定義規(guī)則，由較簡(jiǎn)單的正規(guī)式構(gòu)成的，每個(gè)正規(guī)式e表示一個(gè)語言L(e)（正規(guī)集合）。定義1.15字母表∑上的正規(guī)表達(dá)式和正規(guī)集遞歸定義如下：

1、任意a∈，a是上的一個(gè)正規(guī)表達(dá)式，它所表示的正規(guī)集為{a}。

2、空串ε是∑上的一個(gè)正規(guī)表達(dá)式，它所表示的正規(guī)集為{ε}。

3、符號(hào)φ是∑上的一個(gè)正規(guī)表達(dá)式，它所表示的正規(guī)集為。

4、設(shè)e1與e2都是∑上的正規(guī)表達(dá)式，它們所表示的正規(guī)集分別為L(zhǎng)(e1)與L(e2)，則（1）e1+e2也是正規(guī)表達(dá)式，它所表示的正規(guī)集為

L(e1+e2)=L(e1)∪L(e2)

（2）e1·e2也是正規(guī)表達(dá)式，它所表示的正規(guī)集為

L(e1·e2)=L(e1)L(e2)

（3）(e1)*也是正規(guī)表達(dá)式，它所表示的正規(guī)集為

L((e1)*)=(L(e1))*王雷@版權(quán)所有第二十七頁，共三十七頁，編輯于2023年，星期五1.3正規(guī)表達(dá)式（正規(guī)式

）例1.7

令∑={a,b}，下面表列出了∑上的一些正規(guī)表達(dá)和相應(yīng)的正規(guī)集：王雷@版權(quán)所有正規(guī)表達(dá)式正規(guī)集a+b{a,b}a*{,a,aa,aaa,aaaa,…}aa*{a,aa,aaa,aaaa,…}(a+b)(a+b){aa,ab,ba,bb}(a+b)*{ε,a,b,aa,ab,ba,bb,…}即所有含a和b的符號(hào)串(aa+ab+ba+bb)*空串或任何長(zhǎng)度為偶數(shù)的a,b串(a+b)(a+b)(a+b)*)任何長(zhǎng)度大于等于2的a,b串第二十八頁，共三十七頁，編輯于2023年，星期五1.3正規(guī)表達(dá)式（正規(guī)式

）正規(guī)式的代數(shù)性質(zhì)王雷@版權(quán)所有公理說明r+s=s+r運(yùn)算+是可交換的r+(s+t)=(r+s)+t運(yùn)算+是可結(jié)合的(rs)t=r(st)聯(lián)結(jié)運(yùn)算是可結(jié)合的r(s+t)=rs+rt，(s+t)r=sr+tr聯(lián)結(jié)運(yùn)算對(duì)+運(yùn)算符是可分配的εr=r，rε=r對(duì)于聯(lián)結(jié)而言，ε是單位元r*=(r+ε)*運(yùn)算*和ε的關(guān)系r**=r*運(yùn)算符*是冪等的第二十九頁，共三十七頁，編輯于2023年，星期五1.3正規(guī)表達(dá)式（正規(guī)式

）正規(guī)式和正規(guī)集之間并不存在一一對(duì)應(yīng)的關(guān)系。不同的正規(guī)式可能描述的是相同的正規(guī)集；例如：b(ab)*及(ba)*b都是b開頭且其后跟以零個(gè)或任意多個(gè)ab所組成的字符串兩個(gè)正規(guī)式等價(jià)，當(dāng)且僅當(dāng)它們描述的正規(guī)集相同。

={a,b}上的{a,b}*上的任意一個(gè)子集不一定是正規(guī)集。例如，子集{anbn|n1}就不是一個(gè)正規(guī)集，它不能用正規(guī)式來描述，也不能用正規(guī)文法（3型文法）來描述。因?yàn)檎?guī)文法和正規(guī)式均沒有這樣的能力來判斷或保證a的個(gè)數(shù)等于b的個(gè)數(shù)。但它可用上下文無關(guān)文法（2型文法）S->aSb|ab來描述。王雷@版權(quán)所有第三十頁，共三十七頁，編輯于2023年，星期五1.3正規(guī)表達(dá)式（正規(guī)式

）正規(guī)表達(dá)式運(yùn)算符的優(yōu)先級(jí)順序最高優(yōu)先級(jí)的是閉包運(yùn)算（星閉包*和正閉包+），它類似于代數(shù)運(yùn)算中的冪運(yùn)算。其次優(yōu)先級(jí)的是“聯(lián)結(jié)”運(yùn)算符，它類似于代數(shù)運(yùn)算中的乘法。優(yōu)先級(jí)別最低的是“并”運(yùn)算（+運(yùn)算符）。它類似于代數(shù)運(yùn)算中的加法。通過在正規(guī)表達(dá)式中添加括號(hào)可以改變運(yùn)算的優(yōu)先級(jí)。王雷@版權(quán)所有第三十一頁，共三十七頁，編輯于2023年，星期五1.4正規(guī)文法與正規(guī)式一個(gè)正規(guī)語言可以由正規(guī)文法定義，也可由正規(guī)式定義，對(duì)任意一個(gè)正規(guī)文法，存在一個(gè)定義同一個(gè)語言的正規(guī)式；反之，對(duì)于每一個(gè)正規(guī)式，存在一個(gè)生成同一語言的正規(guī)文法。正規(guī)表達(dá)式和正規(guī)文法之間是可以互相轉(zhuǎn)換的。王雷@版權(quán)所有第三十二頁，共三十七頁，編輯于2023年，星期五1.4正規(guī)文法與正規(guī)式正規(guī)表達(dá)式轉(zhuǎn)換成正規(guī)文法將∑上的一個(gè)正規(guī)表達(dá)式r轉(zhuǎn)換成正規(guī)文法G=（V，T，S，P）的方法如下：

1、令T=∑；

2、選擇一個(gè)非終結(jié)符S，生成規(guī)則Sr，并將S定為G的開始符號(hào)。

3、若x和y都是正規(guī)式，則：

(1)對(duì)形如Axy的規(guī)則，重寫成AxB,，By兩個(gè)規(guī)則，其中B是新選擇的非終結(jié)符，即B∈V。

(2)對(duì)形如A(x+y)B的規(guī)則，重寫成AxB，AyB兩個(gè)規(guī)則。

(3)對(duì)形如Ax+y的規(guī)則，重寫成Ax，Ay兩個(gè)規(guī)則。

(4)對(duì)已轉(zhuǎn)換的文法中形如Ax*y的規(guī)則，重寫成AxA，Ay兩個(gè)規(guī)則。4、不斷利用上述規(guī)則進(jìn)行變換，直到每一條規(guī)則最多有一個(gè)終結(jié)