DEV Community
·
DFA - 确定性有限自动机
💡
原文英文，约300词，阅读约需1分钟。
📝
内容提要
确定性有限自动机（DFA）用于检查语言和模式，以判断输入是否符合预定义规则。DFA由状态集、输入字母表、转移函数、初始状态和接受状态组成。一个示例DFA接受以'a'开头的字符串，其状态转移依据首字母决定接受或拒绝。
🎯
关键要点
- 确定性有限自动机（DFA）用于检查语言和模式，判断输入是否符合预定义规则。
- DFA由状态集、输入字母表、转移函数、初始状态和接受状态组成。
- 示例DFA接受以'a'开头的字符串，如{a, aa, aaa, ab, aabc, ...}。
- 状态转移：初始状态q₀，如果首字母是'a'，转移到接受状态q₁；否则转移到拒绝状态q₂。
- 在接受状态q₁，任何进一步输入都保持在q₁；在拒绝状态q₂，任何进一步输入都保持在q₂。
- 状态图表示：q₀ -- a --> q₁，q₀ -- b --> q₂，q₁ -- (a, b) --> q₁，q₂ -- (a, b) --> q₂。
➡️
