补充资料：概率自动机

概率自动机
automatm, probabilistic

如有限自动机一样，概率自动机可按它们的行为类型分为转换器和接受器.在前一情形，按照功能，概率自动机以某种概率变换输人字到输出字并产生状态字母表中的字.对等长字的这些概率形成一个概率测度，因此这样的行为可以考虑作给出这种测度的可数系.在后一情形，给定终结状态子集S’‘S和称之为割点(cut point)的区间fo，l]中数又.概率接受器饥=(A，S冲，S‘，劝表示的事件由所有这样的A上字组成，在其作用下自动机以至少又的概率进人某个终结状态，其中伊是映射S义A到S的随机函数且由定义在S上的概率测度系叭，。定义.不同于有限自动机，概率自动机可表示事件类是一个连续统.而且，即使是唯一的一个概率自动机，当又变化时也可表示一个连续统事件类.如果输人字母表只含一个字母，则每个概率自动机只表示一个可数事件类，一般地说，也包含非正规事件.在称之为孤立割点的特殊割点上，概率自动机只表示正规事件.区间【O，l]中的一个数又称为给定概率自动机的一个孤立割点(isolated cut加int)，如果存在正数占使得任何输人字变换该概率自动机到它的终结状态的概率与又至少差占. 有限自动机的大部分代表性概念和问题可以不同的作法推广到概率自动机.许多概念和问题保持有限自动机的性质例如，可引入状态的等价概念使得著名的简单试验状态可分性定理仍保持，见自动机的试验(a utomata，experiments with).另一方面，不同于有限自动机，它的极小形式在同构意义下是唯一定义的，对一个给定概率自动机存在等价的极小概率自动机的一个连续统. 存在给出概率自动机的不同形式和方法.例如，一个概率自动机可表示为有两个输人的决定自动机，其中一个输人馈人输人字母的一个随机序列.概率自动机是许多真实机构的数学模型且被用于研究生物体的行为.概率自动机【au舰.la权.，p州babilis血;呵侧盯.川扭-T.ocr服面]，随机自动机(stochastic automaton) 有限自动机(a utomaton，finite)的一种推广，其迁移和输出函数是随机函数换句话说，一个概率自动机可以定义为一个系统(A，S，B冲，们，其中A，S，B是有限字母表具有和有限自动机情形同样的含义，而职和少分别是映射SxA到S和B的随机函数，且分别用S上和B上的概率测度系叭，。和叭，表示，其中a“A，s〔5.这些测度常用随机矩阵给出(见自动机的描述方法(automata，meth侧如ofs讲dficatlon of)).如果这些概率测度只取两个值O和1，则概率自动机概念实际上等同于确定性自动机(d eterministic automaton).无输出的自治概率自动机实质上等同于离散MaP皿oB链.概率自动机的功能的定义类似于非确定性自动机，而且初始状态由S上的一个概率测度叮定义.如果概率自动机处于状态s的概率为p且接收输人字母a，则它以概率p·田(s，a，了，b)进人状态s‘和输出字母表中字母b

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