NFA to DFA (Subset Construction Method)

Posted on   |   In   |  

main idea

  1. Re to NFA
  2. NFA to DFA (Subset Construction Method) (也可以先NFA to NFA without $\varepsilon$)

difference between NFA and DFA

stackoverflow: DFA vs NFA engines: What is the difference in their capabilities and limitations?
DFA没有一个状态具有$\varepsilon$转换，即在输入$\varepsilon$上的转换。对每个状态$s$和输入符号$a$，DFA最多只有一条标记为$a$的边离开，即在任何状态下对任一输入符号，最多只有一个转换。

Example 1 (reference 1)

NFAtoDFA-2
$I$中第一项其实是从state$0$，而$I_a$，$I_b$第一项开始，是从stata $0$开始，经过一个$a$所能到达的几何(可以忽略前后$\varepsilon$)。$b$同理。
NFAtoDFA-1
NFAtoDFA-3
NFAtoDFA-4

Example 2 (reference 2)

NFAtoDFA-1
(rederence 中ppt图有误。)

more example reference 3.

Reference

  1. http://blog.csdn.net/qq_23100787/article/details/50402643
  2. https://raphiinconcordia.files.wordpress.com/2015/05/nfa-to-dfa.ppt
  3. Puntambekar A A. Formal Languages And Automata Theory[M]. Technical Publications, 2008.
  4. Aho A V, 阿霍, Sethi R, et al. 编译原理[M]. 机械工业出版社, 2003.