有限自动机

本文概述

• FA的正式定义
• 有限自动机模型
• 自动机的类型

• 有限自动机用于识别模式。
• 它以符号字符串作为输入，并相应地更改其状态。找到所需符号后，便会发生过渡。
• 在过渡时，自动机可以移至下一个状态或保持相同状态。
• 有限自动机有两种状态，接受状态或拒绝状态。当成功处理输入字符串并且自动机达到其最终状态时，它将接受。

FA的正式定义

有限自动机是5元组（Q，∑，δ，q0，F）的集合，其中：

Q: finite set of states
∑: finite set of the input symbol
q0: initial state 
F: final state
δ: Transition function

有限自动机模型

有限自动机可以用输入磁带和有限控制来表示。

输入胶带：它是具有一定数量单元的线性胶带。每个输入符号放置在每个单元格中。

有限控制：有限控制在从输入磁带接收特定输入时决定下一个状态。磁带读取器从左到右一一读取单元，并且一次只读取一个输入符号。

自动机的类型

有限自动机有两种类型：

1. DFA（确定性有限自动机）
2. NFA（不确定性有限自动机）

1. DFA

DFA是指确定性有限自动机。确定性是指计算的唯一性。在DFA中，机器仅针对特定输入字符进入一种状态。 DFA不接受零举动。

2. NFA

NFA代表非确定性有限自动机。它用于为特定输入传输任何数量的状态。它可以接受零位移动。

关于DFA和NFA的一些重要点：

1. 每个DFA均为NFA，但NFA并非DFA。
2. NFA和DFA中都可以有多个最终状态。
3. DFA用于编译器中的词法分析。
4. NFA更像是一个理论概念。