ac自动机 自动机






zidongji
自动机
automata

   对信号序列进行逻辑处理的装置。在自动机理论中主要是指抽象自动机。抽象自动机是用来表示逻辑关系的动态数学模型,一般都是指能变换和处理信息的离散系统的动态数学模型。在自动控制领域内,自动机是指离散数字系统的动态数学模型,它可定义为一种逻辑结构,一种算法或一种符号串变换。自动机这一术语也广泛出现在许多其他相关的学科中,分别有不同的内容和研究目标。在计算机科学中自动机用作计算机和计算过程的动态数学模型,用来研究计算机的体系结构、逻辑操作、程序设计、乃至计算复杂性理论。在语言学中则把自动机作为,用来研究各种形式语言。在神经生理学中把自动机定义为神经网络的动态模型,用来研究神经生理活动和思维规律,探索人脑的机制。在生物学中有人把自动机作为生命体的生长发育模型,研究新陈代谢和遗传变异。在数学中则用自动机定义可计算函数,研究各种算法。
   自动机的组成和特点  自动机起源于20世纪30年代的,一般都有以下3个组成部分:①输入设备:又称传感器或变送器,相当于生命有机体的感受器,用来接受外界的信息。②输出设备:又称执行器,相当于生命有机体的效应器,用来向外界输出信息,执行各种操作,实现信息的效用。③中央处理器:又称调节器或控制器,相当于生命有机体的神经系统,用来处理、存储和传递信息。现代自动机的一个重要特点是能与外界交换信息,并根据交换得来的信息改变自己的动作,即改变自己的功能,甚至改变自己的结构,以适应外界的变化。也就是说在一定程度上具有类似于生命有机体那样的适应环境变化的能力。
   自动机与一般机器的重要区别在于自动机具有固定的内在状态,即具有记忆能力和识别判断能力或决策能力,这正是现代信息处理系统的共同特点。因此,自动机适宜于作为信息处理系统乃至一切信息系统的数学模型。当自动机与环境进行信息交换时,输出不仅决定于输入,而且也决定于自动机的内在状态。自动机通过内在状态来记忆过去的输入,新的输入又反映在新的内在状态中,因此内在状态起着内存储器的作用。自动机的这种信息变换规律表明,一个自动机可用一个五元组表示:A=(,,,,)。式中、 和分别是状态集、输入集和输出集,和分别是状态转移函数和输出函数,即映射 :×→和:×→。自动机的行为也可以用状态转移图即状态图来表示 (见图[自动机的状态图]的状态图" class=image>)状态图是一种有向图。用节点表示状态,箭头表示状态转移的方向,箭头旁的字符或数字表示输入或输出,视箭头对于节点的向背而定。A能识别 {∈{0,1}| 以11结束且无连续0}。
   自动机分类  自动机可按其变量集和函数的特性分类,也可按其抽象结构和联结方式分类。主要有以下几类:①有限自动机和无限自动机。如果,,都是有限集,则称为有限自动机,又称时序机。如果,,中有一个是无限集,则称为无限自动机。有限自动机是时序网络和一切序储量有限的离散系统的数学模型,如神经网络和语言识别器等。②线性自动机和非线性自动机。如果 和 均是线性函数,则称为线性自动机,否则称为非线性自动机线性自动机便于用线性时序电路来实现,在编码网络、通信网络和计算机控制系统中应用甚广。③确定型自动机和不确定型自动机。如果自动机 A下一内在状态可由当前的输入和当前的内在状态所完全决定,则称A为确定型自动机,否则称A为不确定型自动机。概率自动机和模糊自动机均属于不确定型自动机。概率自动机是指自动机所处环境或其内部有随机因素的自动机。1956年C.E.香农首先把自动机拓展为概率自动机,并证明概率自动机的信息处理能力与有限自动机等价。1968年E.S.桑托斯把自动机拓展为,作为图像识别和学习系统的模型,并证明模糊自动机的识别能力与有限自动机等价。④同步自动机和异步自动机。如果自动机A的状态转移和输出变化均与中央时钟信号同步,即可把时间划分成相等的时间间隔,则称 A为同步自动机。如果自动机 A从一个状态转换到另一个状态的瞬间不能预先确定,即要把时间划分成不相等的时间间隔,则称 A为异步自动机。在许多情况下只要引用抽象自动机时间就可以把异步自动机化为同步自动机来研究。⑤级联自动机和细胞自动机。多台自动机用串联、并联或串并联的方式连接起来,就成为级联自动机。大量的元自动机通过邻域连接方式连接起来,就成为细胞自动机。动态细胞自动机(又称 L系统)可以作为生命体的生长发育模型。
   参考书目
C.E.申南、J.麦克卡赛编,陈中基编译:《自动机研究》,科学出版社,北京,1963。(C.E. Shannonand J.McCarthy(eds), Automata  Studies, PrincetonUniversity Press,Princeton,N.J.,1956.
                 陈中基

以上就是网友分享的关于"自动机"的相关资料,希望对您有所帮助,感谢您对爱华网的支持!

ac自动机 自动机
  

爱华网本文地址 » http://www.aihuau.com/a/337251/57792016855.html

更多阅读

复杂性科学理论框架 复杂性科学微盘

吴晓军,薛惠锋,李 慜(西北工业大学自动化学院,陕西 西安 710072)摘 要:依照复杂性科学的发展脉络,对人工生命研究方法进行了整理、归纳和提升。从主体与规则的演变上总结出了从元胞自动机、群体智慧到复杂适应系统的复杂性科学人工生命的

关于排序网络 算法导论 排序网络

突然发现自己一个礼拜以上没有写日志了,并且上一篇纯属吐槽。不行,不能这么堕落!今天在黑书上看见排序网络。恩。发现真是个好东西。不知道为什么自己特别喜欢像自动机啦,排序网络之类的这种可以实现“自动”干什么什么的,并且能够多次

有关于Saerdna和咖啡&咖啡馆的过去、现在和未来 猫咪咖啡馆

我叫Saerdna,却早已习惯别人叫我小宝,宝哥,宝爷,还有最近又多了一个名字,宝sir,因为我是咖啡行业内的猥小宝,而咖啡占据了我生活和工作的的绝大部分。怀想着曾经一步步走来的历程,也许看起来有点辛酸,但至少我自己一点也不觉得苦。因为这就是

转载 Zigzag指标算法 zigzag扫描实现算法

原文地址:Zigzag指标算法作者:思不得如官方所述:Zigzag指标是连接一系列价格点的趋势线。所以Zigzag主要用途是来标识过去价格中的相对高低点,并以这些点之间的连线来表示这段价格变动的趋势。文章来自:股票自动机-AI Invest:专注于自动

第2节:缓慢和敏感

系列专题:《笑着醒悟的心灵智慧:沉思课》  被加速的人们好比自动机或者机器人。或许你看过卓别林的那部深刻的电影《摩登时代》。查里站在工厂的装配线旁,用一把扳手给经过面前的零件上紧螺丝,一天八小时。每过一阵,老板就会调高传送

声明:《ac自动机 自动机》为网友欧豪呕霸分享!如侵犯到您的合法权益请联系我们删除