确定性有限自动机 (DFA) 是一个五元组
M=(Q, ∑, δ,q0,F)
在哪里，
Q - 称为状态的有限集。
∑ - 称为字母表的有限集。
δ − Q × ∑ → Q 是转移函数。
q0 ∈ Q 是开始或初始状态。
F - 最终或接受状态。
让我们看看语言A∩B 和 A* 的DFA 中最坏情况的状态数
设 A 和 B 为两个状态，
|A| = 状态数 = nA
|乙| = 状态数 = nB
DFA = |A∩B|
=nA.nB
|A ∪ B| =nA.nB
|A*|=3/4 2 nA
|AB| = nA (2 nB -2 nB-1 )
NFA
非确定性有限自动机(NFA)也有五个与 DFA 相同的状态，但具有不同的转换函数，如下所示 -
δ：QX ∑ -> 2 Q
在哪里，
Q - 有限状态集。
∑ - 输入符号的有限集。
q0 - 初始状态。
F - 最终状态。
δ - 过渡函数。
让我们看看语言A∩B 和 A* 的NFA 中最坏情况的状态数
设 A 和 B 为两个状态，
|A| = 状态数 = nA
|B|= 状态数 = nB
NFA：
|AUB| = nA+nB+1
|A*| = nA+1
|AB| = nA+nB
|A∩B| = nA.nB