【有限自动机的可逆性】科学.pdf

有限自动机的可逆性陶仁骥著

前言自动机理论是研究离散数字系统的功能、结构及其两者关系的数学理论.数字电路和数学中的算法,就是离散数字系统的两个典型例子.一个具体的数字电路,无论它多么复杂,其存贮量(记忆元件个数)总是有限的．但是,一个算法执行起来所需要的存贮量,则往往是潜在无穷的.有限自动机(又称时序机、时序电路或时序网络)这个数学概念,是用来描述那些存贮量有限的离散数字系统,作为它们的抽象数学模型的.在三十年代,命题演算(布尔代数)应用于继电器结点网络的分析和综合,形成了开关电路理论.有限自动机理论是开关电路理论的自然发展,在五十年代初,形成了有限自动机的数学概念.

第一章绪论 1有限自动机的逻辑网络实现有限自动机是一种数学动态系统,其示意图如图1.有限自动机具有下述特点:第一,系统的输入、输出和表征系统特征的变量都只取有限种值.第二,时间坐标系统是离散的,由某一个严格上升的非负实数无穷序列t,来规定,只考虑系统的有关变量在这些时刻上的值.第三,在4时刻系统的输入值和表征系统特征的变量的值完全决定了t时刻系统的输出值和+时刻表征系统特征的变量的值,图1 =0,1,.有限自动机用于描述许多具体的离散数字系统,作为它们的抽象数学模型遇到.下面给出有限自动机的严格数学定义.