形式語言基礎(chǔ)

形式語言基礎(chǔ)第一頁，共十九頁，2022年，8月28日第2章形式語言基礎(chǔ)計算機(jī)處理語言，首先應(yīng)考慮語言的形式化、規(guī)范化，使其具有可計算性和可操作性；這就是形式語言理論研究的問題。形式語言誕生于1956年，由chomsky創(chuàng)立。通常，語言研究至少涉及三個方面：語法、語義和語用；這里僅側(cè)重于語法的研究。※形式語言的基本觀點是：語言是符號串之集合！※形式語言理論研究的基本問題是：研究符號串集合的表示方法、結(jié)構(gòu)特性以及運算規(guī)律?！厩把浴康诙摚彩彭?，2022年，8月28日【內(nèi)容提要】第2章形式語言基礎(chǔ)

2.1

形式語言是符號串集合

2.2

形式語言是由文法定義的

2.3

主要語法成分的定義

2.4

兩類特性文法

2.5文法變換方法

2.6關(guān)于形式語言的分類問題第三頁，共十九頁，2022年，8月28日

字母表

--元素(符號)的非空有限集合；符號串

--符號的有限序列；符號串集合

--有限個或者無限個符號串組成的集合；規(guī)則

--以某種形式表達(dá)的在一定范圍內(nèi)共同遵守的章程和制度；這里，指符號串的組成規(guī)則。2.1形式語言是符號串集合

【形式語言】是字母表上的符號，按一定的規(guī)則組成的所有符號串集合；其中的每個符號串稱為句子?！久~解釋】：三要素！第四頁，共十九頁，2022年，8月28日【例2.1】L1={00,01,10,11};

字母表∑1={0,1},

句子有：00,01,10,11【注】⑴b0=（epsilon空符號串）,b1=b,b2=bb,b3=bbb,…⑵L1為有限語言;L2為無限語言。形式語言概念示例：【例2.2】L2={abmc,bn|m>0,n≥0}

字母表∑2={a,b,c},句型1:abmc,有句子：abc,abbc,abbbc,…

句型2:bn;有句子：,b,bb,bbb,…

兩個語言！第五頁，共十九頁，2022年，8月28日1.連接：.=如

a.b=ab

2.1.1符號串(集合)的運算3.

方冪：n=

…

=n-1=n-14.

閉包：n個Ⅰ.符號串的運算

設(shè),為兩個符號串，則：的正閉包：+=1|2|…|n|…的星閉包：*=0|1|2|…|n|…※

0=(空符號串)

什麼符號也沒有的符號串！

1=；2=；…2.

或：|=(或者）這是一種泛指！第六頁，共十九頁，2022年，8月28日2.1.1符號串(集合)的運算(續(xù)1)【例】：⑵ab|cd=ab（或者

cd）⑴abc.de=abcde⑶(a|b)1=(a|b)=a|b

(a|b)*=(a|b)0|(a|b)1|(a|b)2|…(a|b)2=(a|b)(a|b)=aa|ab|ba|bb

…即：(a|b)*=(a|b)n，n≥0同理：(a|b)+

=(a|b)n，n＞0※符號串運算示例泛指：由a，b組成的任意符號串！（包括空串）第七頁，共十九頁，2022年，8月28日1.乘積：

AB={xy|xA且yB}

2.1.1符號串(集合)的運算(續(xù)2)4.閉包：A的正閉包：A+=A1∪A2∪…∪An∪…A的星閉包：A*=A0∪A1∪A2∪…∪An∪…設(shè)A和B

為兩個符號串集合，則：2.和：A∪B=A+B={x|xA或xB}

3.方冪：An=AA…A=AAn-1=An-1An個

※A0={};

A1=A;

A2=AA;A3=AAA;…Ⅱ.符號串集合的運算

第八頁，共十九頁，2022年，8月28日

符號串集合運算示例：【例2.3】設(shè)A={a,b},B={c,d}

則A+B={a,b,c,d}

則AB={xy|xA,yB}={ac,ad,bc,bd}【例2.4】設(shè)A={a}

則A*=A0∪A1∪A2∪…∪An∪…={}+{a}+{aa}+{aaa}+…={,a,aa,aaa,…}={an|n≥0}第九頁，共十九頁，2022年，8月28日【例2.5】設(shè)A={a，b}，A*=?∵A*=A0∪A1∪A2∪…∪An∪…A0={};

A1=A={a，b};A2=A.A={a，b}.{a，b}={aa,ab,ba,bb};A3=A.A2={a，b}.{aa,ab,ba,bb}={aaa,aab,aba,abb,baa,bab,bba,bbb};

…∴A*={x|x=(a|b)n

，n≥0}

符號串集合運算示例(續(xù))：推論：若A為任一字母表,則A*就是該字母表上的所有符號串(包括空串)的集合。第十頁，共十九頁，2022年，8月28日⑴S,A—

定義的對象(S句子,最大的定義對象，又稱為開始符號;A為句型aAc的短語），⑵a,b,c--為字母表∑中的符號;ε-空符號串。⑶->,|--為描述符號(->定義為;|或者是）

2.1.2符號串集合的文法描述【例2.5】L={abnc|n≥0}，

字母表：∑={a,b,c}；

展開：L={ac,abc,abbc,abbbc,…}右圖給出的表示

S->

aAc

A->bA|長久以來，探討符號串集合(即形式語言)的各種描述方法，一直是語言計算機(jī)處理的重要任務(wù)之一。方法

--文法規(guī)則

；其中：第十一頁，共十九頁，2022年，8月28日從開始符號出發(fā)，對符號串中的定義對象，采用推導(dǎo)的方法（用其規(guī)則右部替換左部）產(chǎn)生新的符號串，如此進(jìn)行，直到新符號串中不再出現(xiàn)定義的對象為止，則最終的符號串就是一個句子。

S->

aAcA->bA|規(guī)則應(yīng)用說明示例：

【句子產(chǎn)生過程】(=>推導(dǎo)算符):怎樣利用上述文法規(guī)則表示語言L?①S=>aAc=>aεc=ac②S=>aAc=>abAc=>abεc=abc③S=>aAc=>abAc=>abbAc=>abbc

…一個句子!又一個句子!∴Sabnc,n≥0

=>

+再一個句子!第十二頁，共十九頁，2022年，8月28日

【定義】文法(grammar)是規(guī)則的有限集,其中的上下文無關(guān)文法可定義為四元組：

G(Z)=(VN,VT,Z,P)

VN:非終結(jié)符集（定義的對象集，如：語法成分等)；

VT:終結(jié)符集（字母表）；

Z:開始符號（研究范疇中，最大的定義對象）；

P:規(guī)則集（又稱產(chǎn)生式集）；

A->

或者A->|

其中,描述符號：->(定義為)，|(或者是)

文法符號：Z,A∈VN，,∈(VN+VT)*

2.2形式語言是由文法定義的每個元素每個規(guī)則2.2.1什麼是文法？第十三頁，共十九頁，2022年，8月28日2.2形式語言是由文法定義的（續(xù)3）【注意】提供了規(guī)則集，就相當(dāng)給出了一個文法：

S->

aAc

A->bA|G(S):2.2.2文法是怎樣定義語言的？則L(G)={x|Zx,x∈VT*

}即：一個文法所定義的語言，就是由該文法開始設(shè)有文法G(Z),L(G)為G所定義的語言；VT={a,b,c};Z=S;P:VN={S,A}；G(Z)=(VN,VT,Z,P)利用=>進(jìn)行連續(xù)推導(dǎo)之意！符號推導(dǎo)出的所有僅含終結(jié)符的符號串之集合。其中的每個符號串皆稱為句子。

=>

+〖2.1〗第十四頁，共十九頁，2022年，8月28日【例2.6】標(biāo)識符的文法

【標(biāo)識符】指字母開頭的字母、數(shù)字序列。令G(Z)=(VN,VT,Z,P)則VN={I,A}；

VT={?(字母),d(數(shù)字）}；

Z=I;P:I->?A|?

A->?A|dA|同理，【無符號整數(shù)】文法可寫成：G(N):N->dN|d※其四元組也可寫成：G(N)=({N},hrsu0g8,N,P)第十五頁，共十九頁，2022年，8月28日得：I=?(?|d)n,n≥0令：I=?A|?A=?A|dA|※標(biāo)識符文法所定義的語言求解：上面構(gòu)造的標(biāo)識符文法屬于正規(guī)文法(定義在后)類，正確性檢驗較容易；下面給出一個算法：I->?A|?

A->?A|dA|※求解I值步驟：先求解A:A=(?|d)A,A=(?|d)2A,…,A=(?|d)nA代入A=得：A=(?|d)n,n≥0②∵I=?A|?代入A=(?|d)n,n≥0正規(guī)方程式《標(biāo)識符》：字母開頭的字母、數(shù)字序列；第十六頁，共十九頁，2022年，8月28日則VN={E(算術(shù)表達(dá)式),T(項)，F(xiàn)(因式)}；

VT={i(變量或常數(shù)),+,-,*,/,(,）}；

Z=E;P:【例2.7】簡單算術(shù)表達(dá)式文法【注】此文法定義了算術(shù)表達(dá)式的層次嵌套結(jié)構(gòu):

E->T|E+

T|E-

T

T->F|T*

F|T/

F

F->i|(E)令G(Z)=(VN,VT,Z,P)

(表達(dá)式)表達(dá)式項因式第十七頁，共十九頁，2022年，8月2