有限自动机论
有限自动机论
条目
历史版本
有限自动机论是自动机论的次级学科，研究存储量有限的离散数字系统的功能和结构以及两者的关系。有限自动机也称时序机。
正文
自动机论的次级学科，研究存储量有限的离散数字系统的功能和结构以及两者的关系。
自动电话交换机、开关网络和计算机等物理系统是存储量有限的离散数字系统的实例。有限自动机就是这种有限离散数字系统的抽象数学模型。有限自动机论的主要研究课题是分析和综合问题：给出一个具体的自动机或实现它的逻辑网络，分析有限自动机的功能描述；给出有限自动机的功能描述，综合出能实现此功能的有限自动机，并由此设计出满 足要求的逻辑网络。具体内容有逻辑网络实现、状态化简、状态分配、神经网络、有限接收机和有限自动机的分解等。
发展简况1938年美国科学家C.E.仙农等应用布尔代数对继电路接点电路进行研究，形成了开关网络理论，为有限自动机论的建立奠定了基础。电子数字计算机出现以后，由于对计算机进行逻辑设计的需要，开关网络受到人们普遍重视。50年代中期，美国科学家D.A.赫夫曼和E.F.莫尔各自独立地研究了时序网络理论，形成了有限自动机论的雏形。从此有限自动机论得到深入和系统的研究，已成为自动机论中一个较完整、较成熟的理论。