编译原理中NFA转化为DFA有关问题
编译原理中NFA转化为DFA问题
书上说:把NFA转化为DFA的基本思想是把DFA的每个状态对应于NFA的一个状态集合。
我想问的是:为什么这个基本思想是成立的。
------解决方案--------------------
http://www.chingnotes.com/?p=153 里面有个链接,讲过的。
------解决方案--------------------
状态集合一样代表目前状态可能在的集合是同一个。所以在NFA的转移下,可能可以到达的集合也是同一个。而NFA接受不接受某个字符串只看是否可能到一个接受状态。所以一个状态集合足以表示NFA当前的状态。而状态集合又可以自然的写成一个DFA。所以这就用来把NFA转化成DFA了。
书上说:把NFA转化为DFA的基本思想是把DFA的每个状态对应于NFA的一个状态集合。
我想问的是:为什么这个基本思想是成立的。
------解决方案--------------------
http://www.chingnotes.com/?p=153 里面有个链接,讲过的。
------解决方案--------------------
状态集合一样代表目前状态可能在的集合是同一个。所以在NFA的转移下,可能可以到达的集合也是同一个。而NFA接受不接受某个字符串只看是否可能到一个接受状态。所以一个状态集合足以表示NFA当前的状态。而状态集合又可以自然的写成一个DFA。所以这就用来把NFA转化成DFA了。