自动机导论学习笔记

自动机导论是我在学习编译原理的时候接触的东西。再往前接触的就是图灵机，不过都是非形式化的感性理解。

自动机在编译原理里的主要用途就是用来构造针对三型文法和二型文法识别装置的理论基础。而在此之外，自动机模型也是计算机科学的重要发明，应用很广泛。它不仅作为编译器构造装置，同时也是几种计算模型的形式化定义，并给可计算理论，复杂度理论等提供了基础的支撑。它和语言，文法两个概念紧密相关。

分类

自动机是数字计算机的抽象模型，它在离散的时间框架下，根据外部输入和内部状态将当前内部状态不断地转换为下一个内部状态。其有一些相通的特征：读入装置，存储设备，控制部件，以及其产生的输出。

可以用作分类的要素主要有：

• 状态的有穷/无穷
• 输出方式/临时存储的本质
• 确定/非确定的自动机

有穷自动机

确定型有穷自动机（dfa）是如下的五元组：\(M=(Q, \Sigma, \delta, q_0 , F)\)，这几个符号是自动机，内部状态构成的有限集合，符号的有限集合，状态转移函数（一个定义为\(Q \times \Sigma \to Q\)的全函数），初态（Q中的一个元素），终态集合（Q的一个子集）。

它的工作方式很简单，从初态出发，不断读取输入符号串，根据\(\delta\)的规则，将当前状态根据输入的符号改变为下一个状态。