自动机理论，有穷自动机
各种机器的结构、设计、工作原理在很大程度上取决于其功能目的。区分技术、运输、计算、军事和其他机器。设计用于执行复杂工艺过程的整个自动化复合体被广泛引入各个行业。自动机的设计和构建是为了执行各种逻辑功能（逻辑机器）。
自动机理论 — 控制论部分，这是在数字计算机和控制机器技术要求的影响下产生的。自动机理论中研究的离散自动机是以离散时间步长处理离散（数字）信息的真实系统（包括技术和生物）的抽象模型。
自动机理论基于精确的数学概念，这些概念将关于自动机的功能（行为）及其结构（内部结构）的直观想法形式化。
在这种情况下，信息转换总是被理解为将由输入字母表中的字母组成的输入序列转换为由输出字母表中的字母组成的输出序列的操作。
数理逻辑、代数、概率论、组合数学和图论的工具被广泛使用。
自动机理论的某些部分（自动机结构理论）的问题越来越大 从继电器接触电路的理论，在 1930 年代后期开始形成。包括的 逻辑代数方法.
在自动机的结构理论中，研究了不同类型的方案，旨在描述如何从系统中正确连接的更简单的组件（元素）创建复杂的自动机。
另一个方向，称为自动机抽象理论，研究自动机的行为（即它们进行的信息转换的性质），同时从其内部结构的细节中抽象出来，并出现于 1950 年代。
在自动机抽象理论的框架内，“自动机”和“机器”概念的内容基本上被自动机执行的信息转换的标准描述所穷尽。这种转换可以是确定性的，但也可以是概率性的。
研究最多的是确定性机（自动机），其中包括有穷自动机——自动机理论中的主要研究对象。
有限状态机的特点是内存量有限（内部状态的数量），并使用转换函数定义。通过某种合理的理想化，所有现代数学机器甚至大脑，从其功能的角度来看，都可以被视为有限自动机。
术语“顺序机”、“Milly 自动机”、“摩尔自动机”在文献中（并非所有作者都统一使用）作为术语“有限自动机”的同义词或强调有限转移函数中的某些特征自动机。
具有无限内存的自动机是一种图灵机，能够执行（可能）任何有效的信息转换。 “图灵机”的概念比“有限状态机”的概念出现得早，主要研究算法理论。
抽象自动机理论与著名的代数理论密切相关，例如半群理论。从应用的角度来看，根据内存大小表征自动机中信息转换的结果很有趣。
例如，在自动机实验问题（E.F. Moore 等人的作品）中就是这种情况，其中关于自动机的转换函数或其内存容量的一个或另一个信息是从以下结果中获得的：实验。
另一项任务是根据有关自动机内存大小和输入序列周期的可用信息来计算输出序列的周期。
非常重要的是开发最小化有限状态机的内存和研究它们在随机环境中的行为的方法。
在抽象自动机理论中，综合问题如下。就一些明确形式化的语言而言，条件是为设计的自动机的行为（对于自动机中表示的事件）编写的。在这种情况下，有必要根据每个书面条件开发方法：
1) 找出是否存在这样一个状态机，它所转换的信息满足这个条件；
2) 如果是，则构建这种有限状态机的转换函数或估计其内存大小。
在这种公式中解决综合任务的前提是初步创建一种方便的语言，用于记录自动机的操作条件，并使用方便的算法从记录功能过渡到传递功能。
在自动机的结构理论中，综合问题在于构建给定类型的元素链，实现由其转换函数给定的有限自动机。在这种情况下，他们通常会陈述一些最优性标准（例如，元素的最少数量）并寻求获得最优方案。
后来证明，这意味着早期开发的一些与继电器触点电路相关的方法和概念适用于另一种类型的电路。
随着电子技术的发展，最普遍的方案是 功能元素 （逻辑网络）。逻辑网络的一个特例是抽象神经网络，其元素称为神经元。
已经开发了许多合成方法，这取决于电路的类型和它们预期的信息转换（继电器设备的合成）。
有限状态机 — 具有固定（无法在操作期间增加）内存大小的控制系统的数学模型。
有限状态机的概念是表征一组控制系统（例如，多回路继电器装置）的一般特征的数学抽象。所有这些系统都有共同的特征，这些特征很自然地被接受为有限自动机的定义。
每个完整的自动机都有一个暴露于外部影响和内部元素的入口。对于输入和内部元素，它们可以采用固定数量的离散状态。
输入和内部元素的状态变化发生在离散的时间时刻，其间的间隔称为滴答。磁带末端的内部状态（the state of the internals）完全由内部状态和磁带开头的输入状态决定。
有限自动机的所有其他定义都可以简化为该特征，特别是假设有限自动机的输出取决于给定时间自动机的内部状态的定义。
就这样的特性而言，其输入和内部状态的性质与完整自动机的描述无关。除了输入和状态，您可以只查看随机编号的数字。
如果指定了其内部状态编号对先前内部状态编号和先前输入状态编号的依赖性，则将设置状态机。这样的任务可以采用最终表的形式。
定义完整自动机的另一种常见方法是构造所谓的过渡图。输入状态通常简称为输入，内部状态简称为状态。
有限状态机可以是技术设备和某些生物系统的模型。第一类自动机是，例如，继电器设备和各种电子计算机，包括。 可编程逻辑控制器.
在继电器设备的情况下，输入状态的作用由继电器设备的敏感元件的状态组合来发挥（这种状态的每个组合是一个“复杂状态”，其特征是所有敏感元件的指示他们在给定时刻拥有的这些离散状态）。类似地，继电器设备的中间元件的状态组合充当内部状态。
可编程逻辑控制器 (PLC) 是继电器动作设备的一个示例，可以称为独立状态机。
事实上，程序一旦进入PLC，控制器开始计算，就不受外界影响，后面的状态完全由前面的状态决定。我们可以假设输入在每个时钟周期中都具有相同的状态。
相反，任何具有唯一可能输入状态的有限状态机自然被称为自主的，因为在这种情况下，外部环境不携带控制其行为的信息。
也可以看看：