形式语言与自动机ch34-36

1、12022-3-22College of Computer Science & Technology, BUPT第四节第四节有有 转换的转换的NFAn一、定义一、定义概念：当输入空串概念：当输入空串 (无输入无输入) 时，也能引时，也能引起状态的转移。起状态的转移。例：q2q00q22q00q1q0输入输入“002”时的转移格局：时的转移格局： q0q1q201222022-3-22College of Computer Science & Technology, BUPT - NFA 的形式定义的形式定义 一个一个 - NFA 是一个五元组是一个五元组 A = (Q, T,

2、, q0 , F ). 有限状态集有限状态集 有限输入符号集有限输入符号集 转移函数转移函数 一个开始状态一个开始状态 一个终态集合一个终态集合q0 Q F Q 与与 NFA 的不同之处的不同之处 : Q (T ) 2Q32022-3-22College of Computer Science & Technology, BUPT - NFA 如何接受输入符号串如何接受输入符号串Start0,1, . , 9.0,1, . , 90,1, . , 90,1, . , 9.q1q0q2q3q5 ,+,q4 该该 - NFA 可以接受的字符串如：可以接受的字符串如： 3.14 +.314

3、314.42022-3-22College of Computer Science & Technology, BUPT二、二、 - 闭包（闭包（closure）概念概念 状态状态 q 的的 - 闭包闭包，记为，记为 - CLOSURE 或或ECLOSE ，定义为从，定义为从 q 经所有的经所有的 路径可以到达路径可以到达的状态（包括的状态（包括q自身），自身），如：如： q0q1q2012 - CLOSURE (q0 ) = q0 , q1 , q2 - CLOSURE (q1 ) = q1 , q2 - CLOSURE (q2 ) = q2 52022-3-22College of

4、 Computer Science & Technology, BUPT状态子集状态子集I I 的的-闭包：闭包：-CLOSURE(I) -CLOSURE(q) qI例：例：-CLOSURE(q1，q2) -CLOSURE(q1) -CLOSURE(q2) q1，q2nIa Ia 概念：概念： 对于状态子集对于状态子集I Q，任意任意aT，定义定义Ia如下：如下：Ia= -Closure(P)其中其中P =（I，a）. 即即P是从是从I中的状态经过一条标中的状态经过一条标a的边可以到达的状态集合的边可以到达的状态集合 62022-3-22College of Computer Scie

5、nce & Technology, BUPT例：例：I Iq0q0，q1q1，求求I I1 1I I1 1 -CLOSURE-CLOSURE（I I，1 1） -CLOSURE-CLOSURE（q0q0，q1q1，1 1） -CLOSURE-CLOSURE（q1 q1 ） q1q1，q2q2q0q1q201272022-3-22College of Computer Science & Technology, BUPT扩展转移函数适合于输入字符串扩展转移函数适合于输入字符串 设一个设一个 - NFA, : Q T 2Q 扩充定义扩充定义 : Q T* 2Q 对任何对任何q Q，

6、定义：定义： 1 (q , ) = ECLOSE(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 (包括包括转换在内转换在内) 的路径所能到的路径所能到达的状态达的状态.82022-3-22College of Computer Science & Technology, BUPT-NFA中，中，与与 函数的不同函数的不同 举例举例 计

7、算计算 (q0, a) (q0，)-CLOSURE(q0) q0，q2(q0，a)-CLOSURE(q0，)，a)-CLOSURE(q0，q2，a)-CLOSURE(q0，a) (q2，a)-CLOSURE(q1q3)q1，q2 q3q1，q2，q3 同理：同理：(q0，aa) q3q q0 0q q2 2q q3 3q q1 1abab-CLOSURE(q0)q0，q2-CLOSURE(q1)q1，q2-CLOSURE(q2)q2-CLOSURE(q3)q392022-3-22College of Computer Science & Technology, BUPT三、三、 - N

8、FA 的的 语语 言言 设一个设一个 - NFA M = (Q, T, , q0 , F ) 定义定义 M 的语言：的语言： L(M) = | ( q0 , ) F 即即 满足满足 (q0，) 含有含有F的一个状态的一个状态 102022-3-22College of Computer Science & Technology, BUPT四、有四、有 转换的转换的NFA与无与无 转换的转换的NFA的等价的等价1. -NFANFA具有具有转移的转移的NFA是不具是不具转移的转移的NFA的一般的一般情况，所以只要证明下面的定理即可：情况，所以只要证明下面的定理即可：定理：如果定理：如果L被

9、一个具有被一个具有 转移的转移的NFA接收，接收， 那么那么L可被一个不具可被一个不具 转移的转移的NFA 接收。接收。证明证明思路：构造一个不具思路：构造一个不具 转移的转移的NFA，证明证明其其接收具有接收具有 转移的转移的NFA所接受的语言。所接受的语言。 112022-3-22College of Computer Science & Technology, BUPT从从 - NFA 构造等价的构造等价的 无无 NFA 设设 M = (Q, T, , q0 , F) 是一个是一个 - NFA ，可构造一个无，可构造一个无 的的 NFA M1 = (Q, T, 1 , q0, F

10、1 )， 对任何对任何 a T , 1 (q, a ) = (q , a)。 （注意（注意与与的区别与联系。而的区别与联系。而1和和是相等的。）是相等的。） F1 Fq0 若若-CLOSURE(q0) F F 否则否则122022-3-22College of Computer Science & Technology, BUPT从从 - NFA 构造等价的构造等价的 无无 NFA 证明证明: 采用归纳法证明采用归纳法证明1（q0，）（q0， ），），| |=1|=1。当当| w | = 0, 即即 w = 时，不一定相等时，不一定相等. 1(q0，)q0， 而而(q0，)-CLOSU

11、RE(q0)因此，从因此，从|1开始证明开始证明 当当|=1时，定义相等。时，定义相等。 由由1定义定义 1（q0，a）（q0，a） 132022-3-22College of Computer Science & Technology, BUPT设当设当|=n时，时，1（q0,）=（q0, ），），则则当当|a|=n+1时，时，左侧左侧 1（q0,a）1 (1（q0，），），a)1 (（q0，），），a) 由归纳假设由归纳假设1 (R，a) 设设R（q0，）1 (q，a) q R (q，a) q R. 由由1定义定义 (R，a) (（q0，），），a) R（q0，） (q0，a) 右

12、侧右侧再证再证: 1（q0，）含含F1的一个状态当且仅当的一个状态当且仅当（q0， ）含含F的一的一个状态个状态 （略）（略） 142022-3-22College of Computer Science & Technology, BUPT证明同时展示了一种将证明同时展示了一种将 -NFA转化为转化为NFA的方法的方法. -NFA NFA DFA例：将将 -NFA转换为转换为NFA. （图3.4.1，3.4.3）q0q1q2012q0q1q20120,11,20,1,2152022-3-22College of Computer Science & Technology, B

13、UPT举例举例Start0,1, . ,9.0,1, . ,90,1, . ,90,1, . ,9.q1q0q2q3q5 ,+,q4Startq0 +,-q10,1, . , 9q1 q4.q20,1, . , 9.0,1, . , 9.q2 q3 q50,1, . , 9q3 q50,1, . , 90,1, . , 9162022-3-22College of Computer Science & Technology, BUPT第五节 正则集和正则式正则集：正则集：字母表上一些特殊形式的字符串的集合，字母表上一些特殊形式的字符串的集合，是正则式所表示的集合。是正则式所表示的集合。

14、 正则式正则式：用类似代数表达式的方法表示正则语言。：用类似代数表达式的方法表示正则语言。运算运算: 作用于语言上的三种代数运算作用于语言上的三种代数运算- 联合联合（union）- 连接连接（concatenation）- （星）星）闭包闭包（closure） 172022-3-22College of Computer Science & Technology, BUPT正则表达式（正则表达式（regular expression） 归纳定义归纳定义正则表达式正则表达式如下：如下：基础基础 ：， ，a （aT）都是正则式都是正则式 (原子正则式原子正则式) ，相应的正则集为相应的正

15、则集为， ，a归纳：归纳：如果如果A和和B是正则式，且分别代表集合是正则式，且分别代表集合L(A)和和L(B)， 则则(A+B)，(A.B)， A* 也是正则式，分别表示以下正则集：也是正则式，分别表示以下正则集： L(A) L(B) (语言语言A / 语言语言B的串的串) L(A).L(B) (两个语言中的串的连接两个语言中的串的连接) L(A) * (语言语言A中的串的多次连接中的串的多次连接) 仅通过有限次使用以上两步定义的表达式，才是字母表T上的正则式。这些正则式所表示的字符串集合是T上的正则集。 182022-3-22College of Computer Science &

16、 Technology, BUPT正则表达式算符优先级正则表达式算符优先级 算符优先级（算符优先级（precedence）依次为依次为- （ closure ）- 连接连接（concatenation）- （ union ）定义：若两个正则式表示相同的正则集，则称这两个正则式相等。 即 R1R2 L(R1)=L(R2)注1：正则集是T* 的子集。注2：L+包含当且仅当L包含。注3：每个正则集至少对应一个正则式（可有无穷多个正则式）192022-3-22College of Computer Science & Technology, BUPT正则表达式举例正则表达式举例书书p76 例例

17、1 表示如下语言的正则表达式：语言中的每表示如下语言的正则表达式：语言中的每个字符串由个字符串由交替的交替的 0 s 和和 1 s 构成构成- (01)* + (10)* + 0(10)* + 1(01)*- ( + 1) (01)* ( + 0) - ( + 0) (10)* ( + 1)202022-3-22College of Computer Science & Technology, BUPT语言的语言的联合（联合（union）运算运算 两个语言两个语言 L 和和 M 的联合的联合 L M = w w L w M 举例举例 设设 L = 001,10,111 , M = ,

18、001 ,则则 L M = , 10, 001, 111 212022-3-22College of Computer Science & Technology, BUPT语言的语言的连接（连接（concatenation）运算运算 两个语言两个语言 L 和和 M 的的连接连接 L M = w1w2 w1 L w2 M 有时记有时记 L M 为为 LM 举例举例 设设 L = 001,10,111 , M = , 001 ,则则 LM = 001, 10, 111, 001001, 10001, 111001 222022-3-22College of Computer Science

19、 & Technology, BUPT语言的语言的闭包（闭包（closure）运算运算 语言语言 L 的闭包的闭包 L* = wn w L n 0 , 其中其中wn 为为w 的的 n 次连接次连接 或或 L* = L0 L1 L2 = i 0 Li , 其中其中 L0 = ， L1 = L, L2 = LL, 举例举例 设设 L = 0, 11 , 则则 L* = , 0, 11, 00, 011, 110, 1111, 000, 0011, 0110, 01111, 1100, 11011, 11110, 111111, 232022-3-22College of Computer

20、Science & Technology, BUPT正则式的性质正则式的性质交换律（交换律（commutativity）和结合律和结合律 （associativeity） (1) (+)+(+) (2) ()() (3) +等幂律（等幂律（idempotent law） (4) +分配律（分配律（distributive law） (5) (+)+ (6) (+)+242022-3-22College of Computer Science & Technology, BUPT正则式的性质正则式的性质幺元（幺元（identities）和零元（和零元（annihilators）

21、(7) + (8) (9) 与闭包相关的定律与闭包相关的定律 (10) (*)* (11) *+* * = * = L+ = LL* = L*L （ L+的定义）的定义） L* = L+ + 252022-3-22College of Computer Science & Technology, BUPT正则式的性质正则式的性质 (11) *+* 证明：证明： *2n L(*)L() L(2 ) L(n) L(+*)L() (L() L(2 ) L(n) L() L(*) 而而 L() L(*) +*262022-3-22College of Computer Science &

22、; Technology, BUPT右线性文法右线性文法与与正则式正则式 右右(左左)线性文法又称为正则文法，右线性文法与线性文法又称为正则文法，右线性文法与正则式可以用来代表同一正则语言。二者具有等效正则式可以用来代表同一正则语言。二者具有等效性。性。 例：例： 文法文法 S aS，S a 对应正则式：对应正则式：a+，或者或者a*a272022-3-22College of Computer Science & Technology, BUPT从右线性文法导出正则式从右线性文法导出正则式求解规则求解规则: 设设x = x+，T*，(NT)*, xN 则则x的解为的解为 x*证明：证

23、明：x = x+ 表示表示x有两个生成式：有两个生成式： x x 和和 x ，生成的语言为（生成的语言为（，, ），显然该，显然该语言可用正则式语言可用正则式*表示。表示。书书p78， 例例2书书p79， 例例3282022-3-22College of Computer Science & Technology, BUPT第六节 正则集和右线性文法正则集和右线性文法 正则集是由右线性文法产生的语言正则集是由右线性文法产生的语言 由右线性文法产生的语言都是正则集由右线性文法产生的语言都是正则集(一一). 求证正则集是由右线性文法产生的语言求证正则集是由右线性文法产生的语言证明方法：证明

24、方法： 找出相应的右线性文法，使之产生的语言是这找出相应的右线性文法，使之产生的语言是这些正则集些正则集。292022-3-22College of Computer Science & Technology, BUPT首先从最简单的正则式出发，求证其正则集首先从最简单的正则式出发，求证其正则集，a是右线性语言。是右线性语言。证明：证明：对正则集对正则集，有右线性文法有右线性文法GS，T， ，S， 使使L(G)= 对正则集对正则集,有右线性文法有右线性文法GS，T，S-，S，使使L(G)= 对正则集对正则集a，有右线性文法有右线性文法GS，T，S-a，S，使使L(G)= a 30202

25、2-3-22College of Computer Science & Technology, BUPT将对由并，积，闭包形成的正则集的证明，改为对将对由并，积，闭包形成的正则集的证明，改为对右线性语言的证明。右线性语言的证明。设在字母表设在字母表T上，有语言上，有语言L1和和L2，则则L1 L2，L1.L2，L1*都是右线性语言。都是右线性语言。证明方法：证明方法：分别找出相应的右线性文法。分别找出相应的右线性文法。设设 G1（N1，T，P1，S1）产生产生L1 G2（N2，T，P2，S2）产生产生L2 N1 N2 (若不为空若不为空, 则可对则可对N中符号换名中符号换名)31202

26、2-3-22College of Computer Science & Technology, BUPT构造构造G（N，T，P，S）产生产生L，使使L= L1 L2其中其中 NN1 N2 S, S为新的非终结符；为新的非终结符； PP1 P2 SS1，SS2先证先证L L1 L2：在在G中，由中，由G的定义，对于任意的定义，对于任意，意味着或者（按，意味着或者（按G1的产生式），或者的产生式），或者（按（按G2的产生式）的产生式）即文法即文法G的每个句子或由的每个句子或由G1产生，或由产生，或由G2产生。产生。 L(G) L(G1) L(G2)再证再证 L1 L2 L：设有设有L1 L

27、2，则存在推导则存在推导S1 G1+ 或或 S2 G2+ 必有必有S G+ 。 即即L1 L2 L。 命题得证命题得证 (a). 求证求证L1 L2是右线性语言是右线性语言322022-3-22College of Computer Science & Technology, BUPT 构造构造G（N，T，P，S）其中其中NN1 U N2，SS1，生成式生成式P为为: 若若A-B P1，则它也属于则它也属于P若若A-P1，则则A-S2PP2 P先证先证 L(G1). L(G2) L(G) 若有任意若有任意S1 * 1 与与 S2 * 2 分别属于分别属于G1和和G2定义的语言中，定义的

28、语言中，那么有那么有 S1 1A 2B 3C 1 和和 S2 1A1 2B2 3C3 2 ， S S1 1A 2B 3C 1.S2 * 1. 2 L(G1). L(G2) L(G)(b). 求证求证L1L2是右线性语言是右线性语言332022-3-22College of Computer Science & Technology, BUPT 再证再证 L(G) L(G1). L(G2)若有若有S S1 1A 2B 3C 1.S2 * 1. 2 那么则必然在那么则必然在G1和和G2中同时有中同时有 S1 1A 2B 3C 1 和和 S2 1A1 2B2 3C3 2 L(G) L(G1)

29、. L(G2)命题得证命题得证 (b). 求证求证L1.L2是右线性语言是右线性语言342022-3-22College of Computer Science & Technology, BUPT证明证明: 构造构造G（N，T，P，S） 其中；其中； NN1 U S， S N1，S是一个新的非终结符，是一个新的非终结符， 生成式生成式P为为: 如果如果A - B P1 ，则则A - BP。如果如果A - P1 ，则则A - SPS-S1，S-P。先证先证 L(G) L(G1)*若有若有S S1 1 S * 1 2 S * 1 2 i.S 1 2 i则在则在G1中必然有中必然有 S1 * 1 ； S1 * 2 ； 。；。；S1 * i L(G) L(G1)*(c). 求证求证L1*是右线性语言是右