形式語(yǔ)言與自動(dòng)機(jī)語(yǔ)言及文法課件

引言復(fù)習(xí)：什么是形式語(yǔ)言？什么是文法？什么是自動(dòng)機(jī)？形式語(yǔ)言的定義方式？研究形式語(yǔ)言與自動(dòng)機(jī)的意義？問(wèn)題的提出？本章關(guān)注語(yǔ)言與文法如何描述（產(chǎn)生）左右括號(hào)匹配的語(yǔ)言？如何描述（產(chǎn)生）數(shù)學(xué)表達(dá)式？引言復(fù)習(xí)：1引言知識(shí)點(diǎn)：形式語(yǔ)言所研究的問(wèn)題：產(chǎn)生語(yǔ)言，根據(jù)語(yǔ)言中的基本句子和其它句子的形成“規(guī)則”，得到（產(chǎn)生）語(yǔ)言所包含的所有句子。引言知識(shí)點(diǎn)：2第一節(jié)語(yǔ)言的定義與運(yùn)算一、語(yǔ)言的一些術(shù)語(yǔ)：

字母表：字符的有限集合，記為T(mén)。字符串：由字母表T中的字符構(gòu)成的序列稱(chēng)字母表T上的字符串（句子）。常記為u,v,w,x,y,z；常用a,b,c,d標(biāo)識(shí)單個(gè)字符。第一節(jié)語(yǔ)言的定義與運(yùn)算一、語(yǔ)言的一些術(shù)語(yǔ)：3字母表（Alphabet）

概念

形式符號(hào)的集合

記號(hào)常用T、表示

舉例英文字母表a,b,…,z,A,B,…,Z英文標(biāo)點(diǎn)符號(hào)表,;:.?!’‘“”()…漢字表…,自,…,動(dòng),…,機(jī),…

化學(xué)元素表H,He,Li,…,

T=a,n,y,任,意字母表（Alphabet）概念形式符號(hào)的集合4字符串（string）

概念字母表T上的一個(gè)字符串（簡(jiǎn)稱(chēng)串），或稱(chēng)為字（word），為T(mén)中字符構(gòu)成的一個(gè)有限序列。

空串（emptystring）,用表示，不包含任何字符。

舉例設(shè)T=a,b，則

,

a,ba,bbaba等都是串

字符串w的長(zhǎng)度，記為w，是包含在w中字符的個(gè)數(shù)

舉例=0，bbaba=5ai表示含有i個(gè)a的字符串

字符串（string）概念字母表T上的一個(gè)5

連接（concatenation）

設(shè)x,y為串,且xa1a2…am,yb1b2…bn,則x與y的連接

xya1a2…amb1b2…bn

連接運(yùn)算的性質(zhì)

(xy)z

x（yz

）

xxx

xyx+y

關(guān)于字符串的運(yùn)算連接（concatenation）關(guān)于字符串6

其它如取頭字符，取尾部，子串匹配

等

設(shè)ω1,ω2,ω3是字母表T上的字符串，稱(chēng)：ω1是字符串ω1ω2的前綴，ω2是字符串ω1ω2的后綴，ω2是字符串ω1ω2ω3的子串?？沾侨魏巫址那熬Y，后綴及子串。

例：abc的前綴aababcε.后綴cbcabcε.子串a(chǎn)bcabbcabcε,即一個(gè)字符串可以看作是多個(gè)字符串的連接。

關(guān)于字符串的運(yùn)算其它如取頭字符，取尾部，子串匹配等關(guān)于字7字符串ω的逆用表示。是字符串ω的倒置。ω=b1b2……bn=bnbn-1……b2b1空串ε的逆還是ε字符串ω的逆用表示。是字符串ω的倒置。8字母表的冪運(yùn)算

冪運(yùn)算Tn用來(lái)表示該字母表長(zhǎng)度為n的所有串的集合。設(shè)T為字母表，n為任意自然數(shù)，定義（1）T0=（2）設(shè)x

Tn-1，a

T，則a

x

Tn（3）

Tn中的元素只能由（1）和（2）生成

閉包

T*=

T0T1T2…

閉包

T+=

T1T2T3…

T*=T+，T+=T*

字母表的冪運(yùn)算冪運(yùn)算Tn用來(lái)表示該字母表9閉包的物理意義

T的星號(hào)閉包T*：字母表T上的所有字符串和空串的集合。T的正閉包T+：字母表T上的所有字符串構(gòu)成的集合。 T*=T+∪{ε}舉例設(shè)T=0，1，則T0=，T1=0，1，T2=00，01，10，11，…T*=，0，1，00，01，10，11，…T+=

0，1，00，01，10，11，…閉包的物理意義T的星號(hào)閉包T*：字母表T上的所有字符串10

概念設(shè)T為字母表，則任何集合LT*是字母表T上的一個(gè)語(yǔ)言（language）。隱含的概念：如何表述子集的“特性和規(guī)則”，

舉例-左右括號(hào)的匹配。

英文單詞集…,English,…,words,…

C語(yǔ)言程序集…字母表？漢語(yǔ)成語(yǔ)集…,馬到成功,…

化學(xué)分子式集…,H2O,…,NaCl,…

any,任意

語(yǔ)言（Languages）概念設(shè)T為字母表，則任何集合LT*是11語(yǔ)言（Languages）舉例：設(shè)T={a，b}則L1={anbn|n≥1}L3={bk|k是質(zhì)數(shù)}L2={ε}只有一個(gè)空句子的語(yǔ)言L4={}=Φ空語(yǔ)言均為字母表T上的語(yǔ)言。由語(yǔ)言的定義知語(yǔ)言是集合，對(duì)于集合的運(yùn)算可應(yīng)用于對(duì)于語(yǔ)言的計(jì)算。如并，交，補(bǔ)，差。語(yǔ)言（Languages）舉例：設(shè)T={a，b}12語(yǔ)言的基本運(yùn)算語(yǔ)言的積：

兩個(gè)語(yǔ)言L1和L2的積L1L2是由L1和L2中的字符串連接所構(gòu)成的字符串的集合。即L1中所有字符串分別與L2中的字符串連接得到的集合。設(shè)T={a,b}，L1和L2是T上的語(yǔ)言。L1={ab,ba}L2={aa,bb}則L1L2={abaa,abbb,baaa,babb}L2L1={aaab,aaba,bbab,bbba}L1L2≠L2L1語(yǔ)言的積不可交換。語(yǔ)言的基本運(yùn)算語(yǔ)言的積：13語(yǔ)言的基本運(yùn)算語(yǔ)言的冪： 語(yǔ)言的冪可歸納定義如下: L0={ε}Ln=L·Ln-1=Ln-1·Ln≥1上例中，L12={abab,abba,baab,baba}L22={aaaa,aabb,bbaa,bbbb}

語(yǔ)言的基本運(yùn)算語(yǔ)言的冪：14語(yǔ)言舉例例1：括號(hào)匹配的語(yǔ)言及產(chǎn)生該語(yǔ)言指所有左右括號(hào)相匹配的字符串如何“產(chǎn)生”這個(gè)語(yǔ)言？規(guī)則？遞歸定義提供了集合的定義方式。構(gòu)造規(guī)律?；A(chǔ)：定義該集合的最基本的元素，“（）”遞歸：若S是合法串，則：（S）是合法串； SS是合法串；語(yǔ)言舉例例1：括號(hào)匹配的語(yǔ)言及產(chǎn)生15語(yǔ)言舉例例2：程序設(shè)計(jì)語(yǔ)言中算數(shù)表達(dá)式的語(yǔ)言 運(yùn)算符A：+、-、*、/利用遞歸定義方式。重點(diǎn)是構(gòu)造規(guī)律?；A(chǔ)：?jiǎn)蝹€(gè)變量是最基本的串，i,遞歸：若S是合法串，則：SAS是合法串； （S）是合法串；語(yǔ)言舉例例2：程序設(shè)計(jì)語(yǔ)言中算數(shù)表達(dá)式的語(yǔ)言16語(yǔ)言舉例例3：標(biāo)識(shí)符語(yǔ)言及產(chǎn)生該語(yǔ)言指所有字母開(kāi)頭后接字母或數(shù)字的字符串如何“產(chǎn)生”這個(gè)語(yǔ)言？規(guī)則？遞歸定義提供了集合的定義方式。構(gòu)造規(guī)律?；A(chǔ)：?jiǎn)蝹€(gè)字母是最基本的元素，遞歸：若S是合法串，則：SL是合法串； SD是合法串；L：字母；D：數(shù)字。語(yǔ)言舉例例3：標(biāo)識(shí)符語(yǔ)言及產(chǎn)生17第二節(jié)文法本節(jié)提綱文法的作用文法的形式定義推導(dǎo)與句型文法產(chǎn)生語(yǔ)言第二節(jié)文法本節(jié)提綱182.1文法的作用定義：所謂文法是用來(lái)定義語(yǔ)言的一個(gè)數(shù)學(xué)模型表示語(yǔ)言的方法：若語(yǔ)言L是有限集合，可用列舉法若L是無(wú)限集合（集合中的每個(gè)元素有限長(zhǎng)度），用其他方法。方法一：文法產(chǎn)生系統(tǒng)，由定義的文法規(guī)則產(chǎn)生出語(yǔ)言的每個(gè)句子方法二：機(jī)器識(shí)別系統(tǒng)：當(dāng)一個(gè)字符串能被一個(gè)語(yǔ)言的識(shí)別系統(tǒng)接受，則這個(gè)字符串是該語(yǔ)言的一個(gè)句子，否則不屬于該語(yǔ)言。2.1文法的作用定義：所謂文法是用來(lái)定義語(yǔ)言的一個(gè)數(shù)學(xué)192.1文法的作用---元語(yǔ)言元語(yǔ)言定義：描述語(yǔ)言的語(yǔ)言 例如：各種各樣的程序設(shè)計(jì)語(yǔ)言當(dāng)人們要解釋或討論程序設(shè)計(jì)語(yǔ)言本身時(shí)，又需要一種語(yǔ)言，被討論的語(yǔ)言叫做對(duì)象語(yǔ)言，即某種程序設(shè)計(jì)語(yǔ)言，討論對(duì)象語(yǔ)言的語(yǔ)言稱(chēng)為元語(yǔ)言。2.1文法的作用---元語(yǔ)言元語(yǔ)言定義：描述語(yǔ)言的語(yǔ)言20BNF（巴科斯范式） BNF范式通常被作為討論某種程序設(shè)計(jì)語(yǔ)言語(yǔ)法的元語(yǔ)言<數(shù)字>::=0|1|2|……9::=“定義為”<字母>::=A|B|C|……Z|a|b|……z<標(biāo)識(shí)符>::=<字母>|<標(biāo)識(shí)符><字母>|<標(biāo)識(shí)符><數(shù)字>

….通過(guò)上述定義可知，所有以字母開(kāi)頭的，由字母和數(shù)字組成的字符串都是標(biāo)識(shí)符。BNF定義了一種語(yǔ)言，其中標(biāo)識(shí)符如上定義。BNF描述它所定義的語(yǔ)言，為元語(yǔ)言。BNF（巴科斯范式） BNF范式通常被作為討論某種程序設(shè)21例如：漢語(yǔ)語(yǔ)法中定義了句子的結(jié)構(gòu)由主語(yǔ)、謂語(yǔ)、賓語(yǔ)組成。這里主謂賓只是描述了句子的結(jié)構(gòu)，并不是句子。而按照這種結(jié)構(gòu)組成的建立在漢字上的字符串就是句子。如:他是學(xué)生。例如：漢語(yǔ)語(yǔ)法中定義了句子的結(jié)構(gòu)由主語(yǔ)、謂語(yǔ)、賓語(yǔ)組成。這里22文法是一種元語(yǔ)言，一種定義方法。根據(jù)文法產(chǎn)生出語(yǔ)言的句子。文法是一種元語(yǔ)言，一種定義方法。232.1文法—元語(yǔ)言例如：BNF<標(biāo)識(shí)符>::=<字母><標(biāo)識(shí)符>::=<標(biāo)識(shí)符><字母><標(biāo)識(shí)符>::=<標(biāo)識(shí)符><數(shù)字><字母>::=a|b|……z|A|B|……|Z<數(shù)字>::=0|1|……9將::=改為→表示可被代替用I,L,D分別表示標(biāo)識(shí)符、字母、數(shù)字;2.1文法—元語(yǔ)言例如：242.1文法---元語(yǔ)言則上述表達(dá)式可以表示為 I→LI→ILI→IDL→a|b|….|zD→0|1|….9這就是一個(gè)文法的生成式集合。2.1文法---元語(yǔ)言則上述表達(dá)式可以表示為252.2文法的形式定義Chomsky文法體系中，任何一種文法必須包含有兩個(gè)不同的有限符號(hào)的集合，即非終結(jié)符集合N和終結(jié)符集合T。一個(gè)形式規(guī)則的有限集合P（生成式集合），一個(gè)起始符S。P中的生成式是用來(lái)產(chǎn)生語(yǔ)言句子的規(guī)則，而句子則是僅由終結(jié)符組成的字符串。這些字符串必須從一個(gè)起始符S開(kāi)始，不斷使用P中的生成式而推導(dǎo)出來(lái)?？梢?jiàn)文法的核心是生成式的集合，它決定了語(yǔ)言中句子的產(chǎn)生。2.2文法的形式定義Chomsky文法體系中，任何一種文法262.2文法的形式定義文法G是一個(gè)四元組G=(N，T，P，S)，其中 N非終結(jié)符的有限集合 T終結(jié)符的有限集合N∩T=Φ P形式為α→β的生成式的有限集合。 且α∈(N∪T)*N+(N∪T)*β∈(N∪T)* S起始符且S∈N。2.2文法的形式定義文法G是一個(gè)四元組G=(N，T，P，S27將上例用文法表示 G=(N，T，P，S)N={I,L,D}T={a,b,c,…z,0,1,…9}P={I,La,…,D0,…,D9}S={I}文法是語(yǔ)言的產(chǎn)生系統(tǒng)，研究怎樣構(gòu)造文法能產(chǎn)生出符合要求的句子。將上例用文法表示282.3．推導(dǎo)與句型1、直接推導(dǎo) 設(shè)G=（N,T,P,S）是文法，若A→β是P中的生成式，α和γ是（N∪T）*中的字符串，則有αAγ=>αβγ稱(chēng)αAγ直接推導(dǎo)出αβγ，或說(shuō)αβγ是αAγ的直接推導(dǎo)。2.3．推導(dǎo)與句型1、直接推導(dǎo)29設(shè)G=(N,T,P,S)是文法，α、α0、α1…αn、α’都是（N∪T）*中的字符串，且α=α0、α’=αn，其中αi直接推導(dǎo)出αi+1（0≤i≤n）,則稱(chēng)序列α0=>α1=>α2=>…=>αn是長(zhǎng)度為n的推導(dǎo)序列，而α=α0是長(zhǎng)度為0的推導(dǎo)序列。對(duì)α推導(dǎo)出α’記為αα’，若推導(dǎo)序列長(zhǎng)度大于0，則記為αα’。推導(dǎo)序列的每一步，都產(chǎn)生一個(gè)字符串，這些字符串一般稱(chēng)為句型。2.3、推導(dǎo)序列設(shè)G=(N,T,P,S)是文法，α、α0、α1…αn、α302.3、句型和句子句型 字符串α是文法G的句型，當(dāng)且僅當(dāng)Sα，且α∈（N∪T）*。句子ω是G的句子，當(dāng)且僅當(dāng)Sω,且ω∈T*。（ω是由終結(jié)符組成的字符串）例：I=>L=>a I=>IL=>LL=>zL=>zb句型包含句子2.3、句型和句子句型312.4．文法產(chǎn)生的語(yǔ)言由文法G產(chǎn)生的語(yǔ)言記為L(zhǎng)(G)。 L(G)={ω|ω∈T*且Sω}或： L(G)中的一個(gè)字符串，必是由終結(jié)符組成的，并且是從起始符S推導(dǎo)出來(lái)的。2.4．文法產(chǎn)生的語(yǔ)言322.4文法產(chǎn)生語(yǔ)言例1：括號(hào)匹配的語(yǔ)言及產(chǎn)生遞歸定義提供了集合的定義方式。構(gòu)造規(guī)律?；A(chǔ)：定義該集合的最基本的元素，“（）”遞歸：若S是合法串，則：（S）是合法串； SS是合法串；文法產(chǎn)生式集合：S→（）S→（S）S→SS2.4文法產(chǎn)生語(yǔ)言例1：括號(hào)匹配的語(yǔ)言及產(chǎn)生332.4文法產(chǎn)生語(yǔ)言舉例例2：程序設(shè)計(jì)語(yǔ)言中算數(shù)表達(dá)式的語(yǔ)言 運(yùn)算符A：+、-、*、/利用遞歸定義方式。重點(diǎn)是構(gòu)造規(guī)律。基礎(chǔ)：?jiǎn)蝹€(gè)變量是最基本的串，i,遞歸：若S是合法串，則：SAS是合法串； （S）是合法串產(chǎn)生式集合：S→i;S→SAS;S→(S);A→+;A→?;A→*;A→/;2.4文法產(chǎn)生語(yǔ)言舉例例2：程序設(shè)計(jì)語(yǔ)言中算數(shù)表達(dá)式的語(yǔ)言34第三節(jié)Chomsky文法體系分類(lèi)文法G=(N,T,P,S)；P:α→β 其中α∈（N∪T）*N+（N∪T）*β∈（N∪T）*屬于Chomsky文法體系該體系對(duì)生成式的形式做了一些規(guī)定，分為四類(lèi)，即0型、1型、2型、3型文法0型文法：無(wú)限制文法 對(duì)應(yīng)的語(yǔ)言：遞歸可枚舉語(yǔ)言，與圖靈機(jī)等價(jià)。第三節(jié)Chomsky文法體系分類(lèi)文法G=(N,T,P351型文法也稱(chēng)上下文有關(guān)文法（CSG：Context-sensitiveGrammar) 生成式的形式為α→β， 其中|α|≤|β|，β∈（N∪T）+， α∈（N∪T）*N+（N∪T）*對(duì)應(yīng)的語(yǔ)言：上下文有關(guān)語(yǔ)言（CSL：Context-sensitiveLanguage)若不考慮ε，與線性有界自動(dòng)機(jī)（LBA,LinearBoundedAutomaton）等價(jià)。1型文法也稱(chēng)上下文有關(guān)文法（CSG：Context-sens361型文法語(yǔ)言限定約束：左部的長(zhǎng)度小于右部不含A->ε上下文有關(guān)語(yǔ)言CSL是對(duì)實(shí)際程序語(yǔ)言結(jié)構(gòu)的抽象：典型的這類(lèi)語(yǔ)言結(jié)構(gòu)包括：過(guò)程調(diào)用時(shí)形參與實(shí)參的一致性檢查等。1型文法語(yǔ)言限定約束：372型文法也稱(chēng)上下文無(wú)關(guān)文法（CFG：Context-freeGrammar) A→α, A∈N,且α∈（N∪T）*對(duì)應(yīng)的語(yǔ)言：上下文無(wú)關(guān)語(yǔ)言（CFL：Context-freeLanguage)。對(duì)應(yīng)的自動(dòng)機(jī)：下推自動(dòng)機(jī)（PDA：PushdownAutomaton)。2型文法也稱(chēng)上下文無(wú)關(guān)文法（CFG：Context-free38語(yǔ)言限定約束：左部是1個(gè)非終結(jié)符。CFL對(duì)實(shí)際語(yǔ)言結(jié)構(gòu)的抽象：表示句子的語(yǔ)法結(jié)構(gòu)，如：表達(dá)式，嵌套結(jié)構(gòu){}。目前的程序設(shè)計(jì)語(yǔ)言主要采用CFL描述語(yǔ)法結(jié)構(gòu)。語(yǔ)言限定約束：393型文法也稱(chēng)正則文法右線性文法（Right-linearGrammar）：A→ωB或A→ω A、B∈N,ω∈T*。左線性文法（Left-linearGrammar）： A→Bω或A→ω A、B∈N,ω∈T*。對(duì)應(yīng)的語(yǔ)言：正則語(yǔ)言對(duì)應(yīng)的自動(dòng)機(jī)：有限自動(dòng)機(jī)（FiniteAutomaton）。3型文法也稱(chēng)正則文法40文法舉例例1： G=({A,B,C},{a,b,d},P,A) P:A→AB；AB→CAAB；A→d；B→a；C→b是1型文法。A=>dA=>AB=>dB=>daA=>AB=>ABB=>dBB=>daB=>daaA=>AB=>CAAB=>bAAB=>bdAB=>bdCAAB=>bdbAAB=>bdbdAB=>bdbddB=>bdbdda文法舉例例1：41文法舉例例2： G=({A,B,C},{a,b,c},P,A) P:A→abcA→aBbcBb→bBBc→CbccbC→CbaC→aaBaC→aa是1型文法。 其定義的L={anbncn|n≥1}A=>abcA=>aBbc=>abBc=>abCbcc=>aCbbcc=>aabbcc

文法舉例例2：42文法舉例例3： G=({S,B,C},{a,b},P,A) P:S→aC；S→bB；B→aS；B→bBBB→a； C→bS；C→aCC；C→b是2型文法S=>aC=>abS=>aC=>aaCCS=>aC=>abS=>abaC=>ababS=>ababaC=>abababS=>bB=>bbBB=>bbaSB=>bbaaCB=>bbaabB=>bbaaba文法舉例例3：43文法舉例例4： G=({A,B,C},{a,b,c},P,A)P:A→Ba；A→c；B→Cb；C→c左線性文法L={c,cba}正則語(yǔ)言注意：已知語(yǔ)言求文法，文法不是唯一的，即可以有不同的表達(dá)方法。文法舉例例4：44四類(lèi)文法之間的關(guān)系只是對(duì)生成式形式加以限制0型無(wú)限制1型不允許A→ε形式2型3型屬于2型不含A→ε的2型、3型屬于1型，1型、2型、3型均屬于0型。四類(lèi)文法之間的關(guān)系只是對(duì)生成式形式加以限制45精品課件！精品課件！46精品課件！精品課件！47作業(yè)：P474,6,7題形式語(yǔ)言與自動(dòng)機(jī)語(yǔ)言及文法課件48引言復(fù)習(xí)：什么是形式語(yǔ)言？什么是文法？什么是自動(dòng)機(jī)？形式語(yǔ)言的定義方式？研究形式語(yǔ)言與自動(dòng)機(jī)的意義？問(wèn)題的提出？本章關(guān)注語(yǔ)言與文法如何描述（產(chǎn)生）左右括號(hào)匹配的語(yǔ)言？如何描述（產(chǎn)生）數(shù)學(xué)表達(dá)式？引言復(fù)習(xí)：49引言知識(shí)點(diǎn)：形式語(yǔ)言所研究的問(wèn)題：產(chǎn)生語(yǔ)言，根據(jù)語(yǔ)言中的基本句子和其它句子的形成“規(guī)則”，得到（產(chǎn)生）語(yǔ)言所包含的所有句子。引言知識(shí)點(diǎn)：50第一節(jié)語(yǔ)言的定義與運(yùn)算一、語(yǔ)言的一些術(shù)語(yǔ)：

字母表：字符的有限集合，記為T(mén)。字符串：由字母表T中的字符構(gòu)成的序列稱(chēng)字母表T上的字符串（句子）。常記為u,v,w,x,y,z；常用a,b,c,d標(biāo)識(shí)單個(gè)字符。第一節(jié)語(yǔ)言的定義與運(yùn)算一、語(yǔ)言的一些術(shù)語(yǔ)：51字母表（Alphabet）

概念

形式符號(hào)的集合

記號(hào)常用T、表示

舉例英文字母表a,b,…,z,A,B,…,Z英文標(biāo)點(diǎn)符號(hào)表,;:.?!’‘“”()…漢字表…,自,…,動(dòng),…,機(jī),…

化學(xué)元素表H,He,Li,…,

T=a,n,y,任,意字母表（Alphabet）概念形式符號(hào)的集合52字符串（string）

概念字母表T上的一個(gè)字符串（簡(jiǎn)稱(chēng)串），或稱(chēng)為字（word），為T(mén)中字符構(gòu)成的一個(gè)有限序列。

空串（emptystring）,用表示，不包含任何字符。

舉例設(shè)T=a,b，則

,

a,ba,bbaba等都是串

字符串w的長(zhǎng)度，記為w，是包含在w中字符的個(gè)數(shù)

舉例=0，bbaba=5ai表示含有i個(gè)a的字符串

字符串（string）概念字母表T上的一個(gè)53

連接（concatenation）

設(shè)x,y為串,且xa1a2…am,yb1b2…bn,則x與y的連接

xya1a2…amb1b2…bn

連接運(yùn)算的性質(zhì)

(xy)z

x（yz

）

xxx

xyx+y

關(guān)于字符串的運(yùn)算連接（concatenation）關(guān)于字符串54

其它如取頭字符，取尾部，子串匹配

等

設(shè)ω1,ω2,ω3是字母表T上的字符串，稱(chēng)：ω1是字符串ω1ω2的前綴，ω2是字符串ω1ω2的后綴，ω2是字符串ω1ω2ω3的子串?？沾侨魏巫址那熬Y，后綴及子串。

例：abc的前綴aababcε.后綴cbcabcε.子串a(chǎn)bcabbcabcε,即一個(gè)字符串可以看作是多個(gè)字符串的連接。

關(guān)于字符串的運(yùn)算其它如取頭字符，取尾部，子串匹配等關(guān)于字55字符串ω的逆用表示。是字符串ω的倒置。ω=b1b2……bn=bnbn-1……b2b1空串ε的逆還是ε字符串ω的逆用表示。是字符串ω的倒置。56字母表的冪運(yùn)算

冪運(yùn)算Tn用來(lái)表示該字母表長(zhǎng)度為n的所有串的集合。設(shè)T為字母表，n為任意自然數(shù)，定義（1）T0=（2）設(shè)x

Tn-1，a

T，則a

x

Tn（3）

Tn中的元素只能由（1）和（2）生成

閉包

T*=

T0T1T2…

閉包

T+=

T1T2T3…

T*=T+，T+=T*

字母表的冪運(yùn)算冪運(yùn)算Tn用來(lái)表示該字母表57閉包的物理意義

T的星號(hào)閉包T*：字母表T上的所有字符串和空串的集合。T的正閉包T+：字母表T上的所有字符串構(gòu)成的集合。 T*=T+∪{ε}舉例設(shè)T=0，1，則T0=，T1=0，1，T2=00，01，10，11，…T*=，0，1，00，01，10，11，…T+=

0，1，00，01，10，11，…閉包的物理意義T的星號(hào)閉包T*：字母表T上的所有字符串58

概念設(shè)T為字母表，則任何集合LT*是字母表T上的一個(gè)語(yǔ)言（language）。隱含的概念：如何表述子集的“特性和規(guī)則”，

舉例-左右括號(hào)的匹配。

英文單詞集…,English,…,words,…

C語(yǔ)言程序集…字母表？漢語(yǔ)成語(yǔ)集…,馬到成功,…

化學(xué)分子式集…,H2O,…,NaCl,…

any,任意

語(yǔ)言（Languages）概念設(shè)T為字母表，則任何集合LT*是59語(yǔ)言（Languages）舉例：設(shè)T={a，b}則L1={anbn|n≥1}L3={bk|k是質(zhì)數(shù)}L2={ε}只有一個(gè)空句子的語(yǔ)言L4={}=Φ空語(yǔ)言均為字母表T上的語(yǔ)言。由語(yǔ)言的定義知語(yǔ)言是集合，對(duì)于集合的運(yùn)算可應(yīng)用于對(duì)于語(yǔ)言的計(jì)算。如并，交，補(bǔ)，差。語(yǔ)言（Languages）舉例：設(shè)T={a，b}60語(yǔ)言的基本運(yùn)算語(yǔ)言的積：

兩個(gè)語(yǔ)言L1和L2的積L1L2是由L1和L2中的字符串連接所構(gòu)成的字符串的集合。即L1中所有字符串分別與L2中的字符串連接得到的集合。設(shè)T={a,b}，L1和L2是T上的語(yǔ)言。L1={ab,ba}L2={aa,bb}則L1L2={abaa,abbb,baaa,babb}L2L1={aaab,aaba,bbab,bbba}L1L2≠L2L1語(yǔ)言的積不可交換。語(yǔ)言的基本運(yùn)算語(yǔ)言的積：61語(yǔ)言的基本運(yùn)算語(yǔ)言的冪： 語(yǔ)言的冪可歸納定義如下: L0={ε}Ln=L·Ln-1=Ln-1·Ln≥1上例中，L12={abab,abba,baab,baba}L22={aaaa,aabb,bbaa,bbbb}

語(yǔ)言的基本運(yùn)算語(yǔ)言的冪：62語(yǔ)言舉例例1：括號(hào)匹配的語(yǔ)言及產(chǎn)生該語(yǔ)言指所有左右括號(hào)相匹配的字符串如何“產(chǎn)生”這個(gè)語(yǔ)言？規(guī)則？遞歸定義提供了集合的定義方式。構(gòu)造規(guī)律?；A(chǔ)：定義該集合的最基本的元素，“（）”遞歸：若S是合法串，則：（S）是合法串； SS是合法串；語(yǔ)言舉例例1：括號(hào)匹配的語(yǔ)言及產(chǎn)生63語(yǔ)言舉例例2：程序設(shè)計(jì)語(yǔ)言中算數(shù)表達(dá)式的語(yǔ)言 運(yùn)算符A：+、-、*、/利用遞歸定義方式。重點(diǎn)是構(gòu)造規(guī)律?；A(chǔ)：?jiǎn)蝹€(gè)變量是最基本的串，i,遞歸：若S是合法串，則：SAS是合法串； （S）是合法串；語(yǔ)言舉例例2：程序設(shè)計(jì)語(yǔ)言中算數(shù)表達(dá)式的語(yǔ)言64語(yǔ)言舉例例3：標(biāo)識(shí)符語(yǔ)言及產(chǎn)生該語(yǔ)言指所有字母開(kāi)頭后接字母或數(shù)字的字符串如何“產(chǎn)生”這個(gè)語(yǔ)言？規(guī)則？遞歸定義提供了集合的定義方式。構(gòu)造規(guī)律?；A(chǔ)：?jiǎn)蝹€(gè)字母是最基本的元素，遞歸：若S是合法串，則：SL是合法串； SD是合法串；L：字母；D：數(shù)字。語(yǔ)言舉例例3：標(biāo)識(shí)符語(yǔ)言及產(chǎn)生65第二節(jié)文法本節(jié)提綱文法的作用文法的形式定義推導(dǎo)與句型文法產(chǎn)生語(yǔ)言第二節(jié)文法本節(jié)提綱662.1文法的作用定義：所謂文法是用來(lái)定義語(yǔ)言的一個(gè)數(shù)學(xué)模型表示語(yǔ)言的方法：若語(yǔ)言L是有限集合，可用列舉法若L是無(wú)限集合（集合中的每個(gè)元素有限長(zhǎng)度），用其他方法。方法一：文法產(chǎn)生系統(tǒng)，由定義的文法規(guī)則產(chǎn)生出語(yǔ)言的每個(gè)句子方法二：機(jī)器識(shí)別系統(tǒng)：當(dāng)一個(gè)字符串能被一個(gè)語(yǔ)言的識(shí)別系統(tǒng)接受，則這個(gè)字符串是該語(yǔ)言的一個(gè)句子，否則不屬于該語(yǔ)言。2.1文法的作用定義：所謂文法是用來(lái)定義語(yǔ)言的一個(gè)數(shù)學(xué)672.1文法的作用---元語(yǔ)言元語(yǔ)言定義：描述語(yǔ)言的語(yǔ)言 例如：各種各樣的程序設(shè)計(jì)語(yǔ)言當(dāng)人們要解釋或討論程序設(shè)計(jì)語(yǔ)言本身時(shí)，又需要一種語(yǔ)言，被討論的語(yǔ)言叫做對(duì)象語(yǔ)言，即某種程序設(shè)計(jì)語(yǔ)言，討論對(duì)象語(yǔ)言的語(yǔ)言稱(chēng)為元語(yǔ)言。2.1文法的作用---元語(yǔ)言元語(yǔ)言定義：描述語(yǔ)言的語(yǔ)言68BNF（巴科斯范式） BNF范式通常被作為討論某種程序設(shè)計(jì)語(yǔ)言語(yǔ)法的元語(yǔ)言<數(shù)字>::=0|1|2|……9::=“定義為”<字母>::=A|B|C|……Z|a|b|……z<標(biāo)識(shí)符>::=<字母>|<標(biāo)識(shí)符><字母>|<標(biāo)識(shí)符><數(shù)字>

….通過(guò)上述定義可知，所有以字母開(kāi)頭的，由字母和數(shù)字組成的字符串都是標(biāo)識(shí)符。BNF定義了一種語(yǔ)言，其中標(biāo)識(shí)符如上定義。BNF描述它所定義的語(yǔ)言，為元語(yǔ)言。BNF（巴科斯范式） BNF范式通常被作為討論某種程序設(shè)69例如：漢語(yǔ)語(yǔ)法中定義了句子的結(jié)構(gòu)由主語(yǔ)、謂語(yǔ)、賓語(yǔ)組成。這里主謂賓只是描述了句子的結(jié)構(gòu)，并不是句子。而按照這種結(jié)構(gòu)組成的建立在漢字上的字符串就是句子。如:他是學(xué)生。例如：漢語(yǔ)語(yǔ)法中定義了句子的結(jié)構(gòu)由主語(yǔ)、謂語(yǔ)、賓語(yǔ)組成。這里70文法是一種元語(yǔ)言，一種定義方法。根據(jù)文法產(chǎn)生出語(yǔ)言的句子。文法是一種元語(yǔ)言，一種定義方法。712.1文法—元語(yǔ)言例如：BNF<標(biāo)識(shí)符>::=<字母><標(biāo)識(shí)符>::=<標(biāo)識(shí)符><字母><標(biāo)識(shí)符>::=<標(biāo)識(shí)符><數(shù)字><字母>::=a|b|……z|A|B|……|Z<數(shù)字>::=0|1|……9將::=改為→表示可被代替用I,L,D分別表示標(biāo)識(shí)符、字母、數(shù)字;2.1文法—元語(yǔ)言例如：722.1文法---元語(yǔ)言則上述表達(dá)式可以表示為 I→LI→ILI→IDL→a|b|….|zD→0|1|….9這就是一個(gè)文法的生成式集合。2.1文法---元語(yǔ)言則上述表達(dá)式可以表示為732.2文法的形式定義Chomsky文法體系中，任何一種文法必須包含有兩個(gè)不同的有限符號(hào)的集合，即非終結(jié)符集合N和終結(jié)符集合T。一個(gè)形式規(guī)則的有限集合P（生成式集合），一個(gè)起始符S。P中的生成式是用來(lái)產(chǎn)生語(yǔ)言句子的規(guī)則，而句子則是僅由終結(jié)符組成的字符串。這些字符串必須從一個(gè)起始符S開(kāi)始，不斷使用P中的生成式而推導(dǎo)出來(lái)?？梢?jiàn)文法的核心是生成式的集合，它決定了語(yǔ)言中句子的產(chǎn)生。2.2文法的形式定義Chomsky文法體系中，任何一種文法742.2文法的形式定義文法G是一個(gè)四元組G=(N，T，P，S)，其中 N非終結(jié)符的有限集合 T終結(jié)符的有限集合N∩T=Φ P形式為α→β的生成式的有限集合。 且α∈(N∪T)*N+(N∪T)*β∈(N∪T)* S起始符且S∈N。2.2文法的形式定義文法G是一個(gè)四元組G=(N，T，P，S75將上例用文法表示 G=(N，T，P，S)N={I,L,D}T={a,b,c,…z,0,1,…9}P={I,La,…,D0,…,D9}S={I}文法是語(yǔ)言的產(chǎn)生系統(tǒng)，研究怎樣構(gòu)造文法能產(chǎn)生出符合要求的句子。將上例用文法表示762.3．推導(dǎo)與句型1、直接推導(dǎo) 設(shè)G=（N,T,P,S）是文法，若A→β是P中的生成式，α和γ是（N∪T）*中的字符串，則有αAγ=>αβγ稱(chēng)αAγ直接推導(dǎo)出αβγ，或說(shuō)αβγ是αAγ的直接推導(dǎo)。2.3．推導(dǎo)與句型1、直接推導(dǎo)77設(shè)G=(N,T,P,S)是文法，α、α0、α1…αn、α’都是（N∪T）*中的字符串，且α=α0、α’=αn，其中αi直接推導(dǎo)出αi+1（0≤i≤n）,則稱(chēng)序列α0=>α1=>α2=>…=>αn是長(zhǎng)度為n的推導(dǎo)序列，而α=α0是長(zhǎng)度為0的推導(dǎo)序列。對(duì)α推導(dǎo)出α’記為αα’，若推導(dǎo)序列長(zhǎng)度大于0，則記為αα’。推導(dǎo)序列的每一步，都產(chǎn)生一個(gè)字符串，這些字符串一般稱(chēng)為句型。2.3、推導(dǎo)序列設(shè)G=(N,T,P,S)是文法，α、α0、α1…αn、α782.3、句型和句子句型 字符串α是文法G的句型，當(dāng)且僅當(dāng)Sα，且α∈（N∪T）*。句子ω是G的句子，當(dāng)且僅當(dāng)Sω,且ω∈T*。（ω是由終結(jié)符組成的字符串）例：I=>L=>a I=>IL=>LL=>zL=>zb句型包含句子2.3、句型和句子句型792.4．文法產(chǎn)生的語(yǔ)言由文法G產(chǎn)生的語(yǔ)言記為L(zhǎng)(G)。 L(G)={ω|ω∈T*且Sω}或： L(G)中的一個(gè)字符串，必是由終結(jié)符組成的，并且是從起始符S推導(dǎo)出來(lái)的。2.4．文法產(chǎn)生的語(yǔ)言802.4文法產(chǎn)生語(yǔ)言例1：括號(hào)匹配的語(yǔ)言及產(chǎn)生遞歸定義提供了集合的定義方式。構(gòu)造規(guī)律?；A(chǔ)：定義該集合的最基本的元素，“（）”遞歸：若S是合法串，則：（S）是合法串； SS是合法串；文法產(chǎn)生式集合：S→（）S→（S）S→SS2.4文法產(chǎn)生語(yǔ)言例1：括號(hào)匹配的語(yǔ)言及產(chǎn)生812.4文法產(chǎn)生語(yǔ)言舉例例2：程序設(shè)計(jì)語(yǔ)言中算數(shù)表達(dá)式的語(yǔ)言 運(yùn)算符A：+、-、*、/利用遞歸定義方式。重點(diǎn)是構(gòu)造規(guī)律?；A(chǔ)：?jiǎn)蝹€(gè)變量是最基本的串，i,遞歸：若S是合法串，則：SAS是合法串； （S）是合法串產(chǎn)生式集合：S→i;S→SAS;S→(S);A→+;A→?;A→*;A→/;2.4文法產(chǎn)生語(yǔ)言舉例例2：程序設(shè)計(jì)語(yǔ)言中算數(shù)表達(dá)式的語(yǔ)言82第三節(jié)Chomsky文法體系分類(lèi)文法G=(N,T,P,S)；P:α→β 其中α∈（N∪T）*N+（N∪T）*β∈（N∪T）*屬于Chomsky文法體系該體系對(duì)生成式的形式做了一些規(guī)定，分為四類(lèi)，即0型、1型、2型、3型文法0型文法：無(wú)限制文法 對(duì)應(yīng)的語(yǔ)言：遞歸可枚舉語(yǔ)言，與圖靈機(jī)等價(jià)。第三節(jié)Chomsky文法體系分類(lèi)文法G=(N,T,P831型文法也稱(chēng)上下文有關(guān)文法（CSG：Context-s