形式語(yǔ)言與自動(dòng)機(jī)復(fù)習(xí)大綱.doc

第一章可數(shù)集 Vs. 不可數(shù)集 自然數(shù)集、整數(shù)集、有理數(shù)集市可數(shù)的； 實(shí)數(shù)集是不可數(shù)的 可數(shù)集的冪集是不可數(shù)的語(yǔ)言的概念-斯大林：廣大人群所理解的字和組合這些字的方法。-韋伯斯特：為相當(dāng)大的團(tuán)體的人所懂得并使用的字和組合這些字的方法的統(tǒng)一體。-關(guān)鍵點(diǎn)：字、組成規(guī)則，理解（語(yǔ)義）規(guī)則字母表（alphabet）和字母（letter） 字母表是一個(gè)非空、有窮集合； 字母表中的語(yǔ)言成為該字母表的一個(gè)字母，又叫符號(hào)（symbol）或者字符（character）字母表的乘積 字母表1與2的乘積:12=ab | a1且b2字母表的n次冪1) 0=e. (e表示不包含任何字母的空字符串)2) n=n-1，n1字母表的閉包 字母表的正閉包：+= 23 字母表的克林閉包： *= 0+=023前綴和后綴 設(shè)是一個(gè)字母表，x，y，z*，且x=yz，則稱(chēng)y是x的前綴（prefix），如果ze，則稱(chēng)y是x的真前綴（proper prefix）。z是x的后綴（suffix），如果y e，則稱(chēng)z是x的真后綴（proper suffix）設(shè)有一個(gè)字母表，x,y,z,w,v*,且有x=yz,w=yv,y是x和w的公共前綴，如果x和w的任何公共前綴都是y的前綴，則y是x和w的最大公共前綴。句子的并置與冪 x，y*，x，y的并置（concatenation）是這樣一個(gè)字符串，該串由串x直接連接串y所組成，記作xy。并置也稱(chēng)為連接。(注：并置是定義在字符串上的一種運(yùn)算) 對(duì)于n0，串x的n次冪定義為：x0=；xn=xn-1x。字串（substring） 設(shè)是一個(gè)字母表，w，x，y，z，且w=xyz，則稱(chēng)y是w的字串。語(yǔ)言L*，稱(chēng)L為字母表上的一個(gè)語(yǔ)言（Language）x*，x稱(chēng)為上的一個(gè)句子。不包含任何字符串的語(yǔ)言稱(chēng)作空語(yǔ)言，表示為長(zhǎng)度為0的字符串叫空句子，記作。語(yǔ)言的乘積設(shè)1，2是字母表，語(yǔ)言L1與L2的乘積是一個(gè)語(yǔ)言：則L1L2=xy | xL1,yL2，該語(yǔ)言是字母表12上的語(yǔ)言。*上的并置運(yùn)算具有如下性質(zhì)：對(duì)*上的任意串x,y,z, 結(jié)合律: (xy)z=x(yz) 左消去律: 若xy=xz，則y=z; 右消去律: 若yx=zx，則y=z； 唯一分解性: 存在唯一確定的a1,a2, an使得x=a1,a2, an 單位元素: ex = xe = x 歸納定義（又稱(chēng)遞歸定義，用來(lái)定義一個(gè)集合）的三個(gè)組成部分：基礎(chǔ)：指出某些對(duì)象是該集合的元素，它們是該集合的最基本的元素歸納：指出用集合的元素來(lái)構(gòu)造集合的新元素的規(guī)則。其一般形式為：如果a，b，z是被指定集合的元素，則用某種運(yùn)算或者組合方法對(duì)a，b，z進(jìn)行處理后所得的結(jié)果也是集合中的元素。極小性限定：指出一個(gè)對(duì)象是多定義的集合中的元素的充要條件是該對(duì)象可以通過(guò)有限次地使用基礎(chǔ)和歸納條款中所給的規(guī)定構(gòu)造出來(lái)。歸納定義可用于給出無(wú)窮集合的有窮描述第二章考點(diǎn)：文法的形式定義文法是一個(gè)四元組： G = (V, T, P, S)，其中，V：變量（variables）的非空有窮集。AV，A叫作一個(gè)語(yǔ)法變量（syntactic variable），簡(jiǎn)稱(chēng)為變量，也可叫作非終極符號(hào)（nonterminal）。 T：終極符（teminal）的非空有窮集。要求： aT,a為終極符。 P：由產(chǎn)生式（production）構(gòu)成的非空有窮集合。P的元素均具有形式，讀作定義為，其中，且中至少有V中的一個(gè)元素出現(xiàn)。 。稱(chēng)為產(chǎn)生式的左部，稱(chēng)為產(chǎn)生式的右部。 S：SV，是文法G的開(kāi)始符號(hào)（start symbol）推導(dǎo)的相關(guān)概念（P51）句子與句型 設(shè)文法G=(V,T,P,S)，則稱(chēng)為文法G產(chǎn)生的語(yǔ)言（Language），稱(chēng)為文法G產(chǎn)生的一個(gè)句子（sentence）。設(shè)文法G=(V,T,P,S)，對(duì),若，則稱(chēng)是G產(chǎn)生的一個(gè)句型（sentential form）。文法的推導(dǎo)；正則文法（與右線形文法的轉(zhuǎn)換）；右線性文法。文法的構(gòu)造（例子）。文法的喬姆斯基體系。第三章考點(diǎn)有窮狀態(tài)自動(dòng)機(jī)(finite automaton, FA) 是一個(gè)五元組：M=(Q,q0, F)Q狀態(tài)的非空有窮集合。qQ，q稱(chēng)為M的一個(gè)狀態(tài)(state)。輸入字母表(Input alphabet)。輸入字符串都是上的字符串。 狀態(tài)轉(zhuǎn)移函數(shù)(transition function)，有時(shí)又叫做狀態(tài)轉(zhuǎn)換函數(shù)或者移動(dòng)函數(shù)，:QQ。對(duì)(q,a)Q，(q,a)=p表示M在狀態(tài)q讀入字符a，將狀態(tài)變成p，并將讀頭向右移動(dòng)一個(gè)帶方格而指向輸入字符串的下一個(gè)字符。q0q0Q，是M的開(kāi)始狀態(tài)(initial state)，也可叫做初始狀態(tài)或者啟動(dòng)狀態(tài)。FFQ，是M的終止?fàn)顟B(tài)(final state)集合。qF，q稱(chēng)為M的終止?fàn)顟B(tài)，又稱(chēng)為接受狀態(tài)(accept state)。 對(duì)于x*，如果(q0 , x)F，則稱(chēng) x 被 M 接受，如果(q0 , w)F，則稱(chēng) M 不接受 x。L(M)= x | x*且(q0 ,x)F 稱(chēng)為由 M 接受(識(shí)別)的語(yǔ)言。如果 L(M1) = L(M2)，則稱(chēng) M1 與 M2 等價(jià)。 狀態(tài)轉(zhuǎn)移圖的相關(guān)知識(shí)DFA構(gòu)造的相關(guān)知識(shí)，步驟NFA的基本定義：不確定的有窮狀態(tài)自動(dòng)機(jī)(non-deterministic finite automaton , NFA)M是一個(gè)五元組：M=(Q , , q0 ,F) Q , , q0 , F 的意義同DFA。: Q2Q，對(duì)(q,a)Q，(q,a)= p1 ,p2 , pm表示M在狀態(tài)q讀入字符a，可以選擇地將狀態(tài)變成p1,p2 , , 或者pm ，并將讀頭向右移動(dòng)一個(gè)帶方格而指向輸入字符串的下一個(gè)字符。 根據(jù)NFA構(gòu)造DFA的實(shí)用方法：為了避免不可達(dá)狀態(tài)帶來(lái)的無(wú)用計(jì)算，采用如下策略改進(jìn)定理3-1的構(gòu)造方法：首先，只把狀態(tài)q0填入表的狀態(tài)列中，如果表中的狀態(tài)中有未處理的狀態(tài)，則任選一個(gè)未處理的狀態(tài)q0, , qn，對(duì)中的每個(gè)符號(hào)a，計(jì)算(q0, , qn, a)，并將結(jié)果填入相應(yīng)的表項(xiàng)。如果(q0, , qn, a)在表的狀態(tài)列中未出現(xiàn)過(guò)，則同時(shí)將它填入表的狀態(tài)列。如此重復(fù)下去，直到表的狀態(tài)列中不存在未處理的狀態(tài)。FA與正則語(yǔ)言的相互轉(zhuǎn)換方法（橋梁是右（左）線性文法）。第四章考點(diǎn)：正則表達(dá)式 (regular expression，RE)設(shè)是一個(gè)字母表，(1)是上的正則表達(dá)式，它表示語(yǔ)言；(2)是上的正則表達(dá)式，它表示語(yǔ)言；(3) 對(duì)于 a，a 是上的正則表達(dá)式，它表示語(yǔ)言a；(4)如果 r 和 s 分別是 上表示語(yǔ)言 R 和 S 的 RE，則： r 與 s 的“和” (r+s)是上的RE，(r+s)表達(dá)的語(yǔ)言為RS； r 與 s 的“乘積” (rs)是上的RE，(rs)表達(dá)的語(yǔ)言為RS； r 的克林閉包(r*)是上的RE，(r*)表達(dá)的語(yǔ)言為R*。(5)只有滿足(1),(2),(3),(4)的表達(dá)式才是上的正則表達(dá)式。正則表達(dá)式的定義；正則表達(dá)式等價(jià)的FA的構(gòu)造方法；。第六章考點(diǎn)文法G=(V, T, P, S) 被稱(chēng)為是上下文無(wú)關(guān)的，如果除了形如A的產(chǎn)生式之外，對(duì)于P，均有|，并且V 成立。設(shè)有 CFG G=(V, T, P, S)，G 的派生樹(shù)(derivation tree)是滿足如下條件的(有序)樹(shù)(ordered tree) ：(1) 樹(shù)的每個(gè)頂點(diǎn)有一個(gè)標(biāo)記 X，且 XVT 。(2) 樹(shù)根的標(biāo)記為 S。 (3) 如果一個(gè)非葉子頂點(diǎn) v 標(biāo)記為 A，v 的兒子從左到右依次為 v1 , v2 , , vn，并且它們分別標(biāo)記為 X1 , X2 , , Xn，則AX1X2XnP。(4) 如果 X 是一個(gè)非葉子頂點(diǎn)的標(biāo)記，則 XV。(5) 如果頂點(diǎn) v 標(biāo)記為，則 v 是該樹(shù)的葉子，并且 v 是其父頂點(diǎn)的唯一兒子。 上下文無(wú)關(guān)文法的派生樹(shù)別稱(chēng)生成樹(shù)(derivation tree),分析樹(shù)(parse tree),語(yǔ)法樹(shù)(syntax tree) 順序v1 , v2 是派生樹(shù) T 的兩個(gè)不同頂點(diǎn)，如果存在頂點(diǎn) v，v 至少有兩個(gè)兒子，使得 v1 是 v 的較左兒子的后代，v2 是 v 的較右兒子的后代，則稱(chēng)頂點(diǎn) v1 在頂點(diǎn) v2 的左邊，頂點(diǎn) v2 在頂點(diǎn) v1 的右邊。結(jié)果(yield) 派生樹(shù) T 的所有葉子頂點(diǎn)從左到右依次標(biāo)記為 X1 , X2 , , Xn，則稱(chēng)符號(hào)串 X1X2Xn 是 T 的結(jié)果。 一個(gè)文法可以有多棵派生樹(shù)，它們可以有不同的結(jié)果。稱(chēng) “G的結(jié)果為的派生樹(shù)”為 G 的對(duì)應(yīng)于句型的派生樹(shù)，簡(jiǎn)稱(chēng)句型的派生樹(shù)。規(guī)范派生和規(guī)范規(guī)約；派生和派生樹(shù)的關(guān)系；二義性文法與先天二義性語(yǔ)言；自底向上和自頂向下的分析方法。第七章考點(diǎn)：下推自動(dòng)機(jī) (pushdown automaton，PDA)M = ( Q, q0 , Z0 , F ) Q狀態(tài)的非空有窮集合。qQ，q 稱(chēng)為M 的一個(gè)狀態(tài)(state)；輸入字母表 (input alphabet)。要求 M 的輸入字符串都是上的字符串；棧符號(hào)表 (stack alphabet)。A，叫做一個(gè)棧符號(hào)；Z0Z0叫做開(kāi)始符號(hào)(start symbol)，是 M 啟動(dòng)時(shí)候棧內(nèi)惟一的一個(gè)符號(hào)。所以，習(xí)慣地稱(chēng)其為棧底符號(hào)；q0q0Q，是 M 的開(kāi)始狀態(tài)(initial state)，也可叫做初始狀態(tài)或者啟動(dòng)狀態(tài)；FFQ，是 M 的終止?fàn)顟B(tài)(final state) 集合，簡(jiǎn)稱(chēng)為終態(tài)集。qF，q 稱(chēng)為 M 的終止?fàn)顟B(tài)，也可稱(chēng)為接受狀態(tài) (accept state)，簡(jiǎn)稱(chēng)為終態(tài)。 即時(shí)描述 (instantaneous description，ID) (q, w,)( Q, *,*) 稱(chēng)為 M 的一個(gè)即時(shí)描述。它表示 M 處于狀態(tài) q，w 是當(dāng)前還未處理的輸入字符串，而且 M 正注視著 w 的首字符，棧中的符號(hào)串為，的最左符號(hào)為棧頂符號(hào)，最右符號(hào)為棧底的符號(hào)，較左的符號(hào)在棧的較上面，較右的符號(hào)在棧的較下面。 如果 (p,)(q, a, Z)，a，且 M 在狀態(tài) q、棧頂為 Z、讀入 a 時(shí)，選擇進(jìn)入狀態(tài) p，用替換棧頂 Z，記為(q, aw, Z)M (p, w,)表示 M 做一次非空移動(dòng)，ID從 (q, aw, Z) 變成(p,w,)。如果 (p,)(q,Z)，則記為(q, w, Z)M(p, w,)表示 M 做一次空移動(dòng)，ID從(q, aw,Z)變成 ID(p, w,) 。Mn是M 的 n 次冪：(q1 , w1 ,1)Mn(qn , wn ,n) 存在 ID 序列，并滿