Note for Compiler Design Course in NTHU - Week 5


NFA (with ε closure) 轉 DFA

Minimizing the number of states of a DFA

  • 預設至少兩個 state (至少一個 Final State 和 至少一個 non Final State)
    • 除非證明行為真的不同,只好分更多個 state 出來。
    • Final state 和 non Final state 一定是不同的

Equivalence Classes

Relations and Partitions

  • Partition
    • A partition of a set is a collection of mutually disjoint subsets whose union is the original set.
  • If A is a set with a partition and R is the relation induced by the partition, then R is an equivalence relation.



如果覺得這篇文章對你有幫助, 除了留言讓我知道外, 或許也可以考慮請我喝杯咖啡, 不論金額多寡我都會非常感激且能鼓勵我繼續寫出對你有幫助的文章。

If this blog post happens to be helpful to you, besides of leaving a reply, you may consider buy me a cup of coffee to support me. It would help me write more articles helpful to you in the future and I would really appreciate it.

Related Posts