自然语言处理（三）：自动机理论

前言

判断一个句子是否遵循文法规范，采用自动机是一种较为便捷的途径。针对不同类型的文法，存在相应的自动机用于识别与验证，以下将对四类文法及其对应的四种自动机进行简要说明。

一、有限自动机

确定有限自动机 (Definite Automata, DFA)

确定有限自动机 M 由五个组成部分构成：M = (Σ, Q, δ, q0, F)。其中，Σ 表示输入符号的有限集合；Q 表示状态的有限集合；q0 是 Q 中的一个初始状态；F 是 Q 的子集，代表终止状态集合；δ 是从 Q 与 Σ 的笛卡尔积 Q × Σ 到 Q 的映射函数，用于决定下一个状态。该函数负责调控有限状态控制的行为，通常也被称为状态转移函数。

以上内容为教材中对确定有限自动机的定义，接下来将通过一个具体的图示来进一步阐述五元组所包含的具体含义。

在上述图示中，Σ表示集合{0,1}，Q表示状态集合{A,B}，初始状态q0为A，终止状态集合F为{B}，而δ可以视为一种映射关系。当输入为1时，输出状态为B，记作B = δ(A,1)。

**不确定的有限自动机 (Non-definite A