1、欒 俊3/22/20222022-3-2 敘述由下列正規(guī)式描述的語言0(0|1)*0(|0)1*)*(0|1)*0(0|1)(0|1)0*10*10*10*(00|11)*(01|10)(00|11)*(01|10)(00|11)*)*2022-3-3 一種表述(這里說的01串包括)0(0|1)*0以0開頭和結(jié)尾的長度至少是2的01串(|0)1*)*所有的01串(0|1)*0(0|1)(0|1)倒數(shù)第三位是0的01串0*10*10*10*含有3個1的01串(00|11)*(01|10)(00|11)*(01|10)(00|11)*)*含有偶數(shù)個0和偶數(shù)個1的01串(習(xí)題集P1/1.1)2022

2、-3-4 為下列語言寫正規(guī)定義包含5個元音的所有字母串，其中每個元音只出現(xiàn)一次且按序排列按詞典序排列的所有字母串C語言的注釋相鄰數(shù)字都不相同的所有數(shù)字串最多只有一處相鄰數(shù)字相同的所有數(shù)字串由偶數(shù)個0和偶數(shù)個1組成的所有01串由偶數(shù)個0和奇數(shù)個1組成的所有01串不含字串011的01串2022-3-5 一種答案包含5個元音的所有字母串，其中每個元音只出現(xiàn)一次且按序排列5個元音a, e, i, o, u 不含5個元音的任意字符：B-DF-HJ-NP-TV-Zb-df-hj-np-tv-z，記為*(a|A)*(e|E)*(i|I)*(o|O)*(u|U)*按詞典序排列的所有字母串A*a*B*b*Z*z

3、*C語言的注釋不含/，*的任意字符記為不含*/的任意字符串: (*+/*)*/*(*+/*)*/2022-3-6 一種答案(續(xù))相鄰數(shù)字都不相同的所有數(shù)字串123031357106678035123 0 313571 0 6678 0 353 1 357 1 答案見習(xí)題集P2/1.32022-3-7 一種答案(續(xù))最多只有一處相鄰數(shù)字相同的所有數(shù)字串與上題類似1230313571006678035123 0 313571 00 6678 0 353 1 357 1 answer-double_0|double_1|double_9其中double_i表示相鄰的數(shù)字是idouble_0 - 0?

4、(no_00)*no_000(no_00)*no_0?|00no_0 - 2022-3-8 一種答案(續(xù)) 最多只有一處相鄰數(shù)字相同的所有數(shù)字串(續(xù)) double_i - i?(no_ii)*no_iii(no_ii)*no_i?|ii no_i - (0|no_0_i0)(no_0_i0)*(no_0_i?)|no_0_ino_0_i - no_0-(i-2)_i - no_0-(i+1) - 比如i=5double_5 - 5?(no_55)*no_555(no_55)*no_5?|55 no_5 - 0|no_0_50)(no_0_50)*(no_0_5?)|no_0_5no_0_5-

5、 1|no_0-1_51)(no_0-1_51)*(no_0-1_5?)|no_0-1_5 no_0-1_5-2|no_0-2_52)(no_0-2_52)*(no_0-2_5?)|no_0-2_5no_0-2_5-3|no_0-3_53)(no_0-3_53)*(no_0-3_5?)|no_0-3_5no_0-3_5-4|no_0-54)(no_0-54)*(no_0-5?)|no_0-5no_0-5-2022-3-9 一種答案(續(xù))由偶數(shù)個0和偶數(shù)個1組成的所有01串習(xí)題集P2/1.2由偶數(shù)個0和奇數(shù)個1組成的所有01串習(xí)題集P2/1.22022-3-10 一種答案(續(xù))不含字串011的0

6、1串當出現(xiàn)0后，1只能單獨出現(xiàn)1*(0+1)*0*2022-3-11 用算法2.4為下列正規(guī)式構(gòu)造NFA，并給出處理ababbab的狀態(tài)轉(zhuǎn)換序列(a|b)*(a*|b*)*(|a)b*)*(a|b)*abb(a|b)*2022-3-12 (|a)b*)* ababbab:s-4-0-1-5-6-7-8-4-0-1-5-6-7-6-7-8- 4-0-1-5-6-7-8-f01a234567b58sfstart2022-3-13 可以通過正規(guī)式的最簡DFA同構(gòu)來證明正規(guī)式等價。證明下列正規(guī)式等價(a|b)*(a*|b*)*(|a)b*)*2022-3-14 NFA-DFA1) -closure(s

7、) = s,4,f,0,2,3,5,6,8 = A2) -closure(move(A,a) = -closure(1) = 1,5,6,8,4,f,0,2,3 = B3) -closure(move(A,b) = -closure(7) = 7,6,8,4,f,0,2,3,5 = C4) -closure(move(B,a) = -closure(1) = B5) -closure(move(B,b) = -closure(7) = C6) -closure(move(C,a) = -closure(1) = B7) -closure(move(C,b) = -closure(7) = Cbab abstartCBAa2022-3-15DFA-最簡DFAb1) 劃分為接受狀態(tài)集合F=A,B,C和非接受狀態(tài)S-F=2) 由于S-F為空集，只考慮F： 對于A，輸入a，轉(zhuǎn)換為B，輸入b，轉(zhuǎn)換為C 對于B，輸入a，轉(zhuǎn)換為B，輸入b，