补充资料：有限自动机

有限自动机
automaton, finite

　　和输出通道且在任卜离散时亥U处于n补状态、‘、气之 一的系统这些时刻构成时间集山me se约在越-时刻·些信号即输人卜‘熟件表中的些字母馈入输人通道一井在输出通道产竹些仁、号即输出字母表‘;l的一些字以.在特定观点豁，这种系统可包括形式系统(fo‘Tnal、yste叮z).实际自动书L‘t物体，等等. 有限自动机概念‘耳从不间的观点来定义当采用宏观方法(macro approach)即仅对系统的外部行为感兴趣时，个有限自动机可用一类函数、‘个有限有向图，或(以代数的形式)用一个具有，L运算的有限代数给出〔见自动机的描述方法(au忿。，nata，:nct于1记s。}’spe。万口bon讨’))当采琳微观方法fm:cro ap-proach)时一个有限自动机定义为组儿件和它们的址相连结图式，即不仪考虑自动机的功能.还考虑其结构相应地，这一概念称为结构的(str呱盯a幼而有限自动机本身称为结构自动机‘strudL，ra】aut、)，nata)或自动机网络(automata netw()r括).宏观方法〔macro approac川.个有限自动机就是个系统(斗sB，中，必其中项.S.B是有限字毋表、通常非空，分别称为输人字母表(InPut alPhabet)、状态集(set of srates)和输出字姆表(output alphabct);甲是转移函数(transltlon丘Inet，。n)，‘已映射集合万、』、1到5、中是输出函数怕utput function、.它映射s丫4到B这种有限自动机有时称为Me川y自动机(陇alyautomaton).若输出函数功映射s到B(即不依赖输入字母表的字母)，则此有限自动机称为一个Moore自动机〔Moore automat‘、，。任一Moore自动J丰Jl也址 个Me滋y自动机 一个有限自动机的最重要的特证是它的可上为(见自动机的行为(automaton，behav，our()1 an)).‘〔丁可用不同的方一法定义.取决于所考虑的行为类别，有限自动机可分为转换器，接受器又识别器)产生器，等等为了定义有限自动机行为的主要类型，扩充函数甲和沙到集合S‘通’(其中盛’是4上所有字的集合，包括空字八) 价(、.八少=、，价(、、，a)=价(中(、，，):、杏 劝“八)二产、少卜。的二少(价(、，，)，。)，其中、6泞.，C月几“任刁，仪“表示连接字母a到字之得到的字.因此，函数价(s，a)和价仓、日对任意“和}:的扩充，分别描述自动机在输人字江的作用下从状态s变到的状态和自动机在馈人输人字戊的最后一个字母的时刻所产生的输出字母‘设司。表不字“的长n的开始部分，又设币(sa)和妙(、(动分别为S和B上_定义如下的宁 叫、，a)=甲杯.州，即(、川:)甲(、。)， ，(‘.a)二妙(万，州必(，，司2)‘少仆司.函数不(s，司和丽(s，a)分别描述馈人字:的字母过程中自动机呈现的状态序列，和在输人字“的作用下自动机产生的输出字即输出字母表的字母序列.三元关系 F一{(，，币(，，a)，叭s，。

说明：补充资料仅用于学习参考，请勿用于其它任何用途。