确定型有穷自动机状态极小化的研究  

The Reaesrch of Minimizing Finite Automaton

作　　者：李翰芳[1] 罗幼喜[1] 

机构地区：[1]湖北工业大学理学院,湖北武汉430068

出　　处：《湖北工业大学学报》2009年第4期87-90,共4页Journal of Hubei University of Technology

摘　　要：在树图分割法基础上,对确定型有穷自动机的极小化进行了研究.利用树图分割法,可以在状态的3次方时间内对确定型有穷自动机状态进行极小化.A tree segregated method is introduced in this paper. The equivalent states can be merged so that a small equivalent automaton is produced. The tree segregated algorithm is used to search the evidence which may differentiate the states. The searching process finishes in a square time and the judging process is linear time. Therefore minimizing finite automaton may complete in the condition of cubic time and the language they accept may not he changed.

关 键 词：确定型有穷自动机 等价关系 状态可区分 时间复杂性 树图分割法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]