INT201 W2
This is the note of INT201 Week2. The lecture is still focusing on decision, computation and language.
Alphabet A,
A* = {alll strings consisting symbols from A}
A subset L of A* is called a language
Question: For a language L, does exist an algorithm to check for any x, if x is in L?
Nondeterministic finite automata 非确定性有限自动机
Recall: we took original DFA definition and extended that definition to allow some transitions to be undefined. Nondeterministic Finite Automata (NFA) are a futher extension… 我们采用了原始的DFA定义并扩展了该定义以允许未定义一些转换。非确定性有限自动机是一个进一步的扩展。
- describing a formal language (may be simpler than equivalent DFAs) 描述一种形式语言
- conversion between finite automata and regular expressions 有限自动机和正则表达式之间的转换
“nondeterministic” – an input string does not determine the final state. 一个输入字符串不能决定最终状态。
This is because given a current state and an input letter, we may specify a set of allowable new states, not just one. 这是因为给定一个当前状态和一个输入字母，我们可以指定一组允许的新状态，而不仅仅是一个。
DFA和NFA的区别在于转移函数的类型。不同于DFA对于同一个输入和同一个状态只有一个转移，NFA对于同一输入和同一状态可以有多个或零个转移。DFA的转移必须是一对一的，NFA中的状态转移以集合的形式展现。
Then we say that a NFA accepts an input word w if there exists a sequence of transitions labelled by symbols in w, starting from initial state and ending at some accepting state. 然后我们说一个NFA接受一个输入词w，如果存在一个以w标记的转换序列，从初始状态开始到某个接受状态结束。
通过CSDN上的一篇文章系统的了解了一下NFA和DFA
当输入一个数值的时候，DFA可以转移到固定的状态，但是NFA不可以转移到确定的状态
The formal definition
Let P(S) denote the set of all subsets of a set S. A nondeterministic finite automaton (or NFA) is a quintuple A = (Q,A,φ,i,T) where
- Q is a finite nonempty set whose members are called states of the automaton.
- A is a finite nonempty set called the alphabet of the automaton.
- φ is a map from Q × A to P(Q) called the transition function of the automaton.
- i is a number of Q and is called the initial state.
- T is a nonempty subset of Q whose members are called terminal states or accepting states.
Notation
建议直接看ppt
假设，在一个DFA中，我们可以通过以单词w的字母标记的转换从状态p到状态q，然后我们说状态p和状态q由标记为w的路径连接。
如果w = abc两个中间状态是r1和r2，我们可以把它写成
In a NFA, if φ(p,a) = {q,r} we could write
DFA是一种NFA的约束形式，DFA进行转换的结果集的大小被约束为1或0，因此，DFA接受的语言都被NFA接受。
NFA优缺点: NFA相对于对应的DFA，需要更少的状态，但是这样就会增加搜索的时间。DFA比较快，但不提供Backtrack（回溯）功能，NFA比较慢，但提供了Backtrack功能。
Reference
- XJTLU MC PowerPoint slides (Week2)
- bilibili: NFA to DFA