http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/note.htm
--------------------------------------------------------------------------------------------
3. (太簡單,略)
--------------------------------------------------------------------------------------------
(1)首先畫出最直觀的ab^5和b^2部分
(3) 當然不只ab^7, 要考慮ab^5ab^2和ab^5abab^2這種狀況, 補上一些箭頭
(4) 還要考慮ab^5bbabbab^2和ab^5ab^3這種狀況, 補上一些箭頭
(5) done
--------------------------------------------------------------------------------------------
(b)
首先要先理解本題意思,
它的state要累計兩個值,
一個是a的數量mod3的結果, 一個是b的數量mod3的結果
並且把前者大於後者的state當成final state
(1) 假設遇到a就往下走, 遇到b就往右走,
state的label有2 bits, 第一位記錄n_a mod 3, 第二位記錄n_b mod 3
(2) 當a累積到3個時, 就歸0, 回到舊state
(5) 把前者大於後者的state當成final state, done
--------------------------------------------------------------------------------------------
(9a-1)
首先要清楚這題題意是: 00後面一定要接一個1
換言之, 只要不出現00, 就沒有任何其他強制規定
(9a-2)補上其他線
(9b-1)要求任意長度為4的substring都不能包含超過2個0
因此, 我們需要用state紀錄此字串的最後3碼, 才能知道接下來要走往哪一個state
先列出最危險, 最接近fail的各種狀況
(9b-2) 再列出沒有那麼危險的其他狀況
(9b-3) 補上線
(9b-4) 補上字串一開始進來的其他情況, done
這題的答案給得不夠清楚, 這只是我的答案不保證正確
--------------------------------------------------------------------------------------------
13. 老師上課提到, 當一個L是regular, 它的補集也會是regular
利用這一點, 我們只須證明 L={a^n: n>=0, n=4}是regular
而可以用Formal language表達的language就是regular, 所以只要畫出dfa就得證了(太簡單,略)
14. 同理, 只要畫出dfa就得證了
首先考慮State label應該要有兩bits,
1st紀錄mod3之值, 2st紀錄mod5之值
只要兩bits中有其中一個是0就屬於final states
因為最小公倍數是15, 最多15個states
--------------------------------------------------------------------------------------------
(23a) To prove: 若此language是infinite, 則圖裡一定有cycle
使用反證法(method of contradiction: 非q->非p)：
若圖中沒有cycle->Language must be finite 得證
附註: 數學上的證明除了直接證法(Direct proof), 還有間接證法
間接證法包含反證法(method of contradiction)，歸繆法(Reductio ad Absurdum)和數學歸納法(Proof by induction)等
不同之處在於:
1.直接證法(Direct proof): p->q
2.反證法(method of contradiction) : 非q->非p
3. 歸繆法(Reductio ad Absurdum)： 即矛盾證法，非q and p -> 非p and p (-><-)
(23b) To prove: 若此language是finite, 則圖裡一定沒有cycle
使用反證法(method of contradiction: 非q->非p)：
若圖中有cycle->Language could be finite 得證
--------------------------------------------------------------------------------------------
這題有點廢，它要我們把原本4個states擴展成6個
沒有標準答案，我隨便畫一個：
沒有留言:
張貼留言