本文概述
- FA的正式定义
- 有限自动机模型
- 自动机的类型
- 有限自动机用于识别模式。
- 它以符号字符串作为输入，并相应地更改其状态。找到所需符号后，便会发生过渡。
- 在过渡时，自动机可以移至下一个状态或保持相同状态。
- 有限自动机有两种状态，接受状态或拒绝状态。当成功处理输入字符串并且自动机达到其最终状态时，它将接受。
Q: finite set of states
∑: finite set of the input symbol
q0: initial state
F: final state
δ: Transition function有限自动机模型有限自动机可以用输入磁带和有限控制来表示。
【有限自动机】输入胶带：它是具有一定数量单元的线性胶带。每个输入符号放置在每个单元格中。
有限控制：有限控制在从输入磁带接收特定输入时决定下一个状态。磁带读取器从左到右一一读取单元，并且一次只读取一个输入符号。
文章图片
自动机的类型有限自动机有两种类型：
- DFA（确定性有限自动机）
- NFA（不确定性有限自动机）
文章图片
1. DFA
DFA是指确定性有限自动机。确定性是指计算的唯一性。在DFA中，机器仅针对特定输入字符进入一种状态。 DFA不接受零举动。
2. NFA
NFA代表非确定性有限自动机。它用于为特定输入传输任何数量的状态。它可以接受零位移动。
关于DFA和NFA的一些重要点：
- 每个DFA均为NFA，但NFA并非DFA。
- NFA和DFA中都可以有多个最终状态。
- DFA用于编译器中的词法分析。
- NFA更像是一个理论概念。
