什么是确定性有限自动机 (DFA)？

确定性意味着在每个输入上，只有一个状态，自动机可以从当前状态转换到该状态。在确定性有限自动机中，磁头只能沿一个方向移动以扫描输入磁带符号。但是在扫描输入符号的双向有限自动机的情况下，磁带的头部可能会从其当前位置向右或向左移动。

确定性有限自动机是一组 5 个元组，定义为

M=(Q,Σ,$\delta$,q ₀ ,F) 其中，

• Q：有限控制中存在的非空有限状态集（q ₀，q ₁，q ₂）。

• $\sum$：输入符号的非空有限集。

• $\delta$：它是一个转换函数，有两个参数，一个状态和一个输入符号，它返回一个由 ∴ $\delta$:Q x $\sum$→Q 表示的单个状态。令 q 是状态，a 是传递给转移函数的输入符号。$\delta$(q,a)=q。q 是函数的输出，可能是相同的或新的状态。

• q ₀ ∈ Q 是初始状态。

• F $\subseteq$Q 是最终状态的集合。

示例- 最小化以下 DFA

解决方案：

• 制作一个转换表。

• π ₀ = {{5}}, {1, 2, 3, 4}}

• 对于输入 a，在 π _{0的 {1, 2, 3, 4} 上}

• 对于输入 b，在 π _{0的 {1, 2, 3, 4} 上}

∴ {1, 2, 3, 4} 将被拆分为 {1, 3} 和 {2, 4}

∴ π ₁ ={{5},{1,3},{2,4}}

• 对于 π _{1的 {1, 3} 上的输入符号 a}

同样对于 π _{1的 {2, 4} 上的输入符号 a}

• 对于 π _{1的 {1, 3} 上的输入符号 b}

同样对于 π _{1的 {2, 4} 上的输入符号 b}

π ₁中的子集，即{1, 3} & {2, 4} 不会被拆分。

π_最终= {{5}, {1, 3}, {2, 4}}

DFA 将有 3 个状态。

{5}、{1、3} 和 {2、4}

最小化的 DFA 将是 -