一、什么是NFA和DFA
有限状态自动机（Finite State Machine，FSM）是计算理论中的一种基本模型，可以被形式化描述为一个有限状态集合、接受串集合和转移函数。其中，NFA（Nondeterministic Finite Automata）和DFA（Deterministic Finite Automata）是两种常见的有限状态自动机。NFA允许在同一时间有多个状态可以到达，而DFA每次只能到达唯一的一个状态。
二、NFA和DFA的区别
1. 转移函数的差异
NFA中的转移函数是非确定性的，它可以转移到多个状态，使得在某些情况下，同样的输入可以得到不同的结果。而DFA中的转移函数是确定性的，只能转移到唯一的一个状态，输入相同，结果也相同。
2. 接受条件的定义不同
NFA的接受状态是一组状态，意味着在该状态上，有任何接受条件都是对的。而DFA中只有一个接受状态，只需要状态达到该状态就可以被接受，不存在模糊的状态。
3. 状态转换与终止状态的关系
在NFA的状态转移中，我们可以将多个状态合并成一个状态，使得状态的总数不会太大。但是在DFA中没有这种可能，必须为每种组合都定义一个状态。另外，NFA对于每个状态，都有一个最终状态。而DFA中只有一个接受状态。
三、NFA和DFA的共同点
1. 均可描述为图
NFA和DFA的图模型都是有限状态自动机，也就是状态转移图，可以更好地描述状态和状态之间的关系。基于状态转移图，可以借助图论和图算法来对其进行进一步的建模和分析。
2. 均可以用语言描述
NFA和DFA都可以用自然语言或者正则表达式来表达集合的基本特征和规则，也可以用代码来进行实现。在实际应用中，我们可以根据不同的场景和需求，灵活使用NFA和DFA，来实现对应的算法和模型。
四、NFA和DFA的代码实现
1. NFA的代码示例
class NFA:
def __init__(self, states, alphabet, transitions, start, accepting):
"""
Initialize an NFA with its components.
states - a set of hashable states
alphabet - a set of hashable symbols
transitions - a dictionary of sets of state pairs.
Keys are (state, symbol) pairs, values are sets of states
start - a start state from states
accepting - a set of accepting states from states
"""
self.states = states
self.alphabet = alphabet
self.transitions = transitions
self.start = start
self.accepting = accepting
def _move(self, states, symbol):
"""
Given a set of states and a symbol to read, return a set of states
that we could transit to
"""
return set.union(*(self.transitions.get((state, symbol), set()) for state in states))
def accepts(self, string):
"""
Determine if this NFA will accept a given string
"""
current_states = {self.start}
for symbol in string:
current_states = self._move(current_states, symbol)
return bool(current_states & self.accepting)
2. DFA的代码示例
class DFA:
def __init__(self, states, alphabet, transitions, start, accepting):
"""
Initialize a DFA with its components.
states - a set of hashable states
alphabet - a set of hashable symbols
transitions - a dictionary of dictionaries.
Keys are states, values are dictionaries
Keys in the value dictionaries are symbols
Values in the value dictionaries are states
start - a start state from states
accepting - a set of accepting states from states
"""
self.states = states
self.alphabet = alphabet
self.transitions = transitions
self.start = start
self.accepting = accepting
def _move(self, state, symbol):
"""
Given a state and a symbol to read, return the state we will be in
after reading it
"""
return self.transitions[state][symbol]
def accepts(self, string):
"""
Determine if this DFA will accept a given string
"""
current_state = self.start
for symbol in string:
current_state = self._move(current_state, symbol)
return current_state in self.accepting
