一个非确定的有穷洎动机(NFA)M是一个五元式：

• S是一个有限集它额每个元素称为一个状态。
• ∑是一个有穷字母表它的每个元素称为一个输入字符
• δ是一个从S×∑?至S子集额单值映射。即：δ:S×∑?→2?S
• S0?S,是一个非空的初态集

定义对状态集合I的几个有关运算：

• 状态集合I的ε-闭包表示为ε-closure(I)，定义为一状态集是状态集I中的任何状态s经任意条ε弧而能到达的状态的集合。状态集合I的任何状态s都属于ε-closure(I)
• 状态集合I的a弧转换，表示为move(I,a)定义为状态集合J其中J是所有那些可从I的某一状态经过一条a弧而到达的状态的全体。 
  

• 每次从队头取出一个集合(开始队列內只有初态集合I的ε-闭包(I)
• 然后如果当前状态之前没有出现过，那么当前状态作为一个新的状态I,放入队列
• 一直做如上操作，直到队列为空

一个确定的有穷自动机(DFA)M是一个五元式：

• S是一个有限集，它的每个元素称为一个状态
• ∑是一個有穷字母表，它的每个元素称为一个输入字符 
  －δ是一个从S×∑至S的单值映射δ(s,a)=s’意味着：当现行状态－为s、输入字符为a时，将转换箌下一个状态s’我们称s’为s的一个后继状态。
• s0∈S是唯一的初态。

• 1.构造状态的初始划分∏0：终态kt 和非终态K- kt两组
• 2.对∏施用传播性原则 构造新划分∏new
new=∏,则令∏new=∏并继续步骤4否则∏:=∏new重复2 final中的每一组选一代表，这些代表构成M’的状态若k是一代表且f(k,a)=t,令r是t组的代表，则M’中有一转换f’(k,a)=r M’ 的开始状态是含有K0的那组的代表 M’的终态是含有Kt的那组的代表
• 5.去掉M’中的死状态.

已知一个正则表达式,把它转化为nfa,nfa转化为dfa,dfa最小化 评分:

已知一个正则表达式,把它转化为nfa,nfa转化为dfa,dfa最小化 用!

已知一个正则表达式,把它轉化为nfa,nfa转化为dfa,dfa最小化