2006/09/09

又來了

一般的 finite automata 是 deterministic finite automata(DFA),而有種 non-deterministic finite automata(NFA)能自己在過程中分裂成多個 DFA,所以顯然 DFA 是 NFA 的特化;然而經過證明,任何 NFA 都能轉換為計算能力等價的 DFA ─ 因此 NFA 等價於 DFA。又是「一即全體」的情形(cf. the MVT family)。下一節是 regular expressions,先整理一下到目前所學:

  • 定義:DFA
  • 定義:NFA
  • 定義:DFA 認得(recognizes)某個字串
  • 定義:NFA 認得(recognizes)某個字串
  • 定理:NFA ==> DFA
  • 定義:regular language
  • 每部 DFA 都認得恰好一種(one and only one)language
  • 作用於 languages 的三種操作:聯集(union)、串接(concatenation)、星號(star)
  • 定理:三種操作對於 regular languages 的封閉性

雖然寫得很有趣,這本書和所有類似書籍一樣(不是它們的錯),不太能明確揭示「所呈現理論」在整體科學邏輯網內的角色,這有待自己思考。

--
再搭配 Visual Automata Simulator,automata 真的很好玩 XD。

Blogger Airman Of Chunghua WIND9/09/2006 1:37 pm 說:

這篇幾乎看不懂 Orz..

---
這檔案不能拿來抵帳喔!

 
Blogger Josh Ko9/09/2006 1:49 pm 說:

我懶得把定義定理證明抄上來了,自己看書 XD。

 
Blogger yen39/10/2006 3:04 pm 說:

那麼我們可不可以懶的看這篇..XD

 

<< 回到主頁