Research Space for Linear Algebra & Discrete Mathematics
假設不存在>0的simple circuit，又E不空，
在G中找一條maximal path from A->…->D，A!=D
則in-degree(D)!=out-degree(D)，矛盾
1. (4)(a) 0ε1=01∈A, 1ε0=10∈A, 根據inductive case, 將兩個串連起來, 1001∈A(b) 對遞迴的次數 n 做歸納證明, 當 n=0 時字串為ε顯然成立, 然後假設 n=k 時 ok, 再對 k+1 次遞迴時分別檢查 0x1, 1x0, xy 這三種狀況都會符合 0 與 1 出現的次數一樣多, 即完成證明2. (2.2)有 S->0A 但是也有 S->1A, 所以開頭可以是 0 也可以是 1, 再對 A 稍微推導一下可導出這題的答案是(b)3. (5)證明OK, 但再寫得清楚一點會更好, 最好再詳細說明一下為什麼找出那一條maximal path之後會導致 in-degree(D) 不等於 out-degree(D)4. (3.6)因為 δ 有 n^mn 種可能, s 有 n 種可能, F 有 2^n 種可能, 所以總共會有 (n^mn)(n)(2^n) 種不同的DFA
張貼留言
1 則留言:
1. (4)
(a) 0ε1=01∈A, 1ε0=10∈A, 根據inductive case, 將兩個串連起來, 1001∈A
(b) 對遞迴的次數 n 做歸納證明, 當 n=0 時字串為ε顯然成立, 然後假設 n=k 時 ok, 再對 k+1 次遞迴時分別檢查 0x1, 1x0, xy 這三種狀況都會符合 0 與 1 出現的次數一樣多, 即完成證明
2. (2.2)
有 S->0A 但是也有 S->1A, 所以開頭可以是 0 也可以是 1, 再對 A 稍微推導一下可導出這題的答案是(b)
3. (5)
證明OK, 但再寫得清楚一點會更好, 最好再詳細說明一下為什麼找出那一條maximal path之後會導致 in-degree(D) 不等於 out-degree(D)
4. (3.6)
因為 δ 有 n^mn 種可能, s 有 n 種可能, F 有 2^n 種可能, 所以總共會有 (n^mn)(n)(2^n) 種不同的DFA
張貼留言