1、第二章 語言與文法 概念復習字母表字符串語言: 字母表T*的子集語言運算: 同集合運算。并、交、連接、冪（正閉包、*閉包）、補、差文法: G=( N，T，P，S )文法的分類:¨ 0型文法(無限制文法)¨ 1型文法(上下文有關文法):生成式: ， |， 且（NT）+， （NT）*N+（NT）*¨ 2型文法(上下文無關文法): A, AN, 且（NT）*¨ 3型文法(正則文法):右線性文法: AB 或 A，A、BN, T*。左線性文法：AB 或 A，A、BN, T*。對應的語言：正則語言對應的自動機：有限自動機練習1. 設文法 G (S，A, a, b,

2、P, S ) 的產生式P為：S àS à aSS à bAA à bAA à 說明其產生的語言形式。練習2 語言L中的每個串由零個或多個0, 緊跟一個或多個1, 然后再緊跟兩個或多個2構成。試定義該語言的一個上下文無關文法。練習3 給出T=a,b 上能滿足下列條件的語言的文法：（1） 至少有3個a的所有符號串（2） a的個數不多于3的所有符號串練習4 給出T=a 上能滿足下列條件的語言的文法：（1） L=w | |w| mod 3 =0 （2） L=w | |w| mod 3 >0 （3） L=w | |w| mod 3 <>

3、 |w| mod 2 第三章 有限自動機和右線性文法概念復習：¨ 有限狀態系統可以認為有限狀態系統定義了一個無窮的語言，這個語言是由那些能使狀態從初始狀態經過任意可能的路徑到達終止狀態的字符串組成。¨ 有限自動機( DFA / NFA ):五元組 M（Q，T，q0，F） DFA: : Q×T -> QNFA: : Q×T -> 2Q¨ 格局: 表現自動機所處工作狀態 (q，)雙向自動機的格局: (1q2)¨ 自動機接受的語言：對DFA L(M)|(q0,) F對NFA L(M)|(q0,) 含F的一個狀態接受一個字符的狀態

4、轉換函數 - 接受一個字符串的狀態轉換函數 - (q,a)（(q,), a）¨ NFA 到DFA的轉換(子集構造法) (實踐中最好方法是從q0出發)練習1. 構造一個自動機，使它接受下面的字符集R|0，1* ,恰好包含一個“00”而不含“000”序列練習2. 設字母表T=a, b , 對語言G = 含有3個連續b的所有字符串的集合, 分別寫出其NFA和 DFA .概念復習：¨ 轉換:當輸入空串(無輸入)時,也能引起狀態的轉移.¨ 閉包:狀態q的-閉包：-CLOSURE(q) - 表示從q出發可用轉換到達的所有狀態的集合狀態子集I 的-閉包：-CLOSURE(I)

5、-CLOSURE(q) qI¨ 有轉換的NFA中，與 函數的區別: 是接受字符串的狀態轉移函數： Q×T* -> 2Q' (q，) p1 ，p2 ， pn （路徑中含有標的邊）（1）.' (q，)-CLOSURE(q)（2）.' (q，a)-CLOSURE(P)其中P p | 存在r'(q，) p(r，a)注意：此時(q，a) ¹'(q，a)，因為(q，a)表示由q出發，只沿著標a 的路徑所能到達的狀態，而'(q，a)表示由q出發，沿著標a (包括轉換在內) 的路徑所能到達的狀態.¨ 有轉換的NFA所

6、能接受的語言:L（M）| $p（p'(q0，) pF）（即滿足' (q0，) 含有F的一個狀態）¨ 有轉換的NFA 到無轉換的NFA 的等效:設具有轉移的NFA： M（Q，T，q0，F）可構造不具有轉移的NFA：M1（Q，T，1，q0，F1）, 其中F1 ì Fq0 若-CLOSURE(q0) 含F中一個狀態 í î F 否則1（q，a）（q，a）概念復習：¨ 正則集與正則式字母表上一些特殊的字符串的集合稱為正則集。表示正則集可用正則式。正則集是正則式所表示的集合。關鍵：用類似代數表達式的方法來表示正則集。¨ 定義：

7、字母表T上的一個正則式及它們所代表的正規集合可以遞歸地定義如下:(1) ，a （aT）都是正則式 (原子正則式) ，相應的正則集為，a(2) 如果A和B是正則式，且分別代表集合L(A)和L(B)，則(A+B)，(A.B), A* 也是正則式，分別表示正則集 (語言)L(A) L(B) 語言A / 語言B的串L(A).L(B) 兩個語言中的串的連接L(A) * 語言A中的串的多次連接(3) 僅通過有限次使用以上兩步定義的表達式，才是字母表T上的正則式。這些正則式所表示的字符串集合是T上的正則集。¨ 正則式的性質若兩個正則式表示相同的正則集，則稱兩個正則式相等。正則集是T* 的子集。 定

8、義 L0， L1L， LiL.Li-1 L+包含當且僅當L包含。每個正則集至少對應一個正則式（可有無窮多個正則式）；每個正則式只對應一個正則集。¨ 由正則文法求解正則式右線性文法與正則式具有等效性。即可以用來代表同一正則語言。求解規則: 設x->x+，T*，(N+T)*, xN (更嚴格地說，應為和為正則表達式）則x的解為 x*練習3 設正則文法G的產生式為:S à 0A | 1S |A à 0B | 1AB à 0S | 1B , 求解其正則式.右線性文法與正則集的等價¨ 一個右線性文法表示的語言可以用正則式來表示(求解聯立方程)¨ 一個用正則式表示的語言可以用右線性文法來表示¨ 右線性文法與正則式兩者等價，進而它們與FA等價。¨ FSM的局限性:必須是有限個狀態 (但其語言可以是無限的).正則表達式和有限自動機u 已知正則式，構造NFAu 已知DFA，構造等價正則式右線性語言與有限自動機u 已知右線性文法，構造NFAu 已知DFA，構造右線性文法右線性