补充资料：自动机的等价

自动机的等价
automata, equivalence of

题和方法，适当地考虑它们的特点，通常可以扩展到自动机的其他类型，作为参考可见自动机(a utomaton). B .B.K〕吸PJ.习eB，幻.H.枷oB撰【补注】读者可参看条目形式语言(font以1』angi坦笋)和L系统(L一systems).本条中的大部分课题已不再看作是现在的主流.自动机的等价[au翻”nata，equl司en沈of;~~，曰...nellTI，川，，‘] 在自动机集上的一个等价关系，由于研究自动机的某些特殊的内在性质所引起.这样的一种性质通常是自动机的行为(automaton，behaviour ofan)，因此，两个自动机看作等价的，倘若它们的行为相同.此时，一个自动机的行为通常理解为由它实现的全体函数，见有限自动机(a utomaton，finite).对有限自动机来说，这样一个等价关系是可解的.所以，存在一个自动机的极小化算法，即用来对任一给定自动机构造一个最小可能状态数的等价自动机(极小自动机)的算法. 自动机的等价性可依据状态的等价(e quivalenceofstates)概念方便地定义:自动机吸和班‘(它们可以相同)的两个状态s和s’称为等价的，倘若初始自动机级:和纵奋实现相同的函数.自动机级和罗等价意味着跳的任一个状态可找到级’的一个状态等价于它，反之亦然.一个自动机是极小的当且仅当它没有不同的两个等价状态.在同构意义下，任何一个自动机的极小自动机唯一确定.有限自动机的这一等价关系的求解算法基于Moore定理(Moore theorem).按照这一定理，级的状态s和s’等价如果初始自动机级，和甄实现的函数在长n一1的字上一致，其中n是跳的状态数.如果状态s和s’分属两个自动机跳和吸’，则字长等于”+n’一1，其中n’是级’的状态数.著名的有限自动机极小化算法也是基于这一定理.该算法构造所谓的归约自动机(red眠d automaton)，其状态是状态等价类，而它的迁移函数和输出函数由原来的自动机的对应函数自然诱导出.归约自动机是极小的，因为它的任何两个不同状态是不等价的. 对具有n个状态，m个输入字母和p个输出字母的极小自动机的个数A(m，n，P)，存在它的渐近估计.如果m+n+p~的，对m)3，有估计A(m，n，P)一(陀P)阴”/”!，而 ，‘。二、_。，/(劫，区变巴 A“，”，P)~“‘’-一石丁·在自动机的等价性研究中的另一个问题是自动机的等价变换(equivalent transfonnations)问题.这个问题对有限自动机的两种可能的定义方法—图和逻辑网络—都已被研究.一般来说，问题是要求出一组变换规则，它们满足某些条件并可应用它们将任何给定自动机变换到任一个等价于它的自动机:所谓的完全规则组.在两种情形下，变换规则都是一对图式(图或逻辑网络的片断)，它们实现相同的映射.此规则的应用是用一个片断代替另一个片断.对有限自动机来说，完全规则组不存在，但对限制延迟数的逻辑网络来说，则是存在的. 在有限自动机的等价性研究中出现的基本概念、问

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