自动机

问:关于自动机的理解

答:计算机控制系统的控制程序具有有限状态自动机（FA）的特征，可以用有限状态机理论来描述。有限自动机（Finite Automata Machine）是计算机科学的重要基石，它在软件开发领域内通常被称作有限状态机（Finite State Machine），是一种应用非常广泛的软件设计模式。

问题:自动机理论的内容是什么?

回答:

常见自动机有以下几种:以电话交换机为主要实例的有限自动机，是自动机理论的基础，被应用到自动控制，生物系统中；由下推表组成的单项非确定程序的下推自动机；线性有界自动机；用来描述通用计算机计算能力的图灵机模型；进行与转移函数，转移状态有关输出的时序机；由一些基本语句构成程序框图的波斯特机；随即存储机；堆栈自动机；不受有限自动机做控制器和存储限制的无限自动机；统计自动机某一条件概率分布的概率自动机和细胞自动机。

数理语言学中研究抽象自动机的理论。抽象自动机是一种能够识别语言的抽象的装置，它不是具有物理实体的机器，而是表示计算机运算方式的抽象的逻辑关系系统，这样的抽象自动机可以用来检验输入的符号串是不是语言中合格的句子，如果是合格的句子，自动机就接收它，如果不是，就不接收它。

自动机可分为有限自动机、后进先出自动机、线性有界自动机、图灵机等几种。它们对语言的识别能力各不相同。

有穷自动机

问题:什么是NFA?

回答:NFA的另一种意思就是不确定有穷自动机，一般采用tompson构造来构建NFA。

NFA＝Nondeterministic Finite Automata

一个不确定的有穷自动机T是一个五元组，M＝｛K，∑，f，S，Z｝

⒈K是一个有穷集他的每一个元素称作一个状态。

⒉∑是一个字母表，他的每一个元素称为一个输入符号。

⒊f是一个从Kx∑*到K的子集映射即K*∑*-＞2＾K，其中2＾K表示K的幂集。

⒋S包含于K集，是一个非空初态集合。

⒌Z包含于K是一个非空的终态集合。

问题:有穷自动机的概念?

回答:有穷自动机，或有穷状态的机器，是描述（或“机器”）特定类型算法的数学方法,是关于存储量及其有限的计算机的很好的模型。。特别地，有穷自动机可用作描述在输入串中识别模式的过程，因此也能用作构造扫描程序。

什么是有穷自动机?

答:有穷自动机是关于存储量极其有限的计算机的很好的模型。一台计算机用如此小的存储能做些什么呢?回答是:能做很多有用的事情！事实上，我们时时刻刻都要和这样的计算机打交道，因为它们存在于各种各样的机电设备的核心部位。

问题:有穷自动机的分类?

回答:确定有穷自动机和不确定有穷自动机。

问:有穷自动机与图灵机的区别?

答:1）图灵机在带子上既能写也能读

2）读写头既能向左移也能向右移

3）带子是无限长的

4）进入拒绝和接受状态将立即停机

图灵机与自动机的区别:

图灵机的作用就是识别语言，与自动机是类似的。不过有一些语言自动机无法识别，而图灵机却可以识别，图灵机的能力当然要强过自动机。

问题:什么是正则语言（regular language）?

答:如果一个语言被一台有穷自动机识别，则称它是正则语言。

有限状态机

问题有限状态自动机的动作有?

 答:

进入动作:在进入状态时进行；

退出动作:在退出状态时进行；

 输入动作:依赖于当前状态和输入条件进行；

 转移动作:在特定转移时进行。

问:什么是有限状态机?

答:有限状态机（FSM），又称有限状态自动机，简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。

状态存储关于过去的信息，就是说:它反映从系统开始到现在时刻的输入变化。转移指示状态变更，并且用必须满足来确使转移发生的条件来描述它。

什么时有限状态机?

有限状态机，（英语:Finite-state machine， FSM），又称有限状态自动机，简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。

问:有限状态机的作用是什么?

答:它对数字系统的设计具有十分重要的作用。

有限状态机是指输出取决于过去输入部分和当前输入部分的时序逻辑电路。一般来说，除了输入部分和输出部分外，有限状态机还含有一组具有“记忆”功能的寄存器，这些寄存器的功能是记忆有限状态机的内部状态，它们常被称为状态寄存器。在有限状态机中，状态寄存器的的下一个状态不仅与输入信号有关，而且还与该寄存器的当前状态有关，因此有限状态机又可以认为是组合逻辑和寄存器逻辑的一种组合。其中，寄存器逻辑的功能是存储有限状态机的内部状态；而组合逻辑又可以分为次态逻辑和输出逻辑两部分，次态逻辑的功能是确定有限状态机的下一个状态，输出逻辑的功能是确定有限状态机的输出。