1. hint: dfa的特色就是, 所有的{a,b}都要畫出來(即使是無意義的not-accepted),也就是一個state 都必須split出兩條線, 一條a一條b, 不能多也不能少
所以就連sink也要畫一條線寫a,b指向自己喔!!
(a)少畫了!!
2. hint:
(1) dfa不允許λ (2)dfa每條路都一定要走出去
8.
Pumpimg Lemma複習:
已知一個regular language L 有以下性質,
有一個數字m(此數字通常指dta的state數目)
若有一個string w屬於L且規定 |w| >= m
那麼w可以被拆成x,y,z三部分, let w=xyz
其中 |xy| <= m (規定的,這樣等下才能套用pigeon hole) 且 |y|>0 (y一定至少要一個字元)
則一個正規語言會滿足 : { w^i = x y^i z | i是任意正整數 } 全部必須屬於L
若違反了它, 就不是正規語言
Q. 證明L={a^nb^n}不是regular
(1) 假設L為regular
(2) 取一個m, 令m=n
(3) 因為|xy| 必須要<= m, 所以y落在a^n的區間
(4) 令y=a, x=a^5, z=a^(m-6)b^m
(5) w^i = x (y^i) z
(6) 當i>1時, 不符合language a^nb^n的形式, 違反Pumpimg Lemma, 所以L不是regular
所以簡單來說就是,
必須先找一個符合language格式的string w, 再取一個假設的正整數m
並且要保證 w的長度大於等於m, 再想辦法將w切成x,y,z 3部分, 改寫成wi = x y^i z的形式
最後只要能找到一個 i >=0 使得wi不符合 language的string格式,
就可以說它違反Pumpimg Lemma, 所以L不是regular
沒有留言:
張貼留言