一种基于树结构的Muller自动机确定化方法

本发明提供了一种基于树结构的Muller自动机确定化方法包括：构造初始状态树作为确定性自动机的初始状态；从预定义的字母表中读出字母并将其赋予初始状态树以改变其结构从而重新生成状态树，均作为确定性自动机的一个新状态以此扩充状态集合，并记录转换过程中状态树的迁移信息；从状态集合中提取状态树读入字母表中字母重新生成状态树以更新状态集合；重复该过程直至未产生新的状态树得到最终状态集合及迁移集合；将迁移集合中的迁移分配至最终状态集合中相应节点对应的集合对，从而定义确定性自动机的接收条件。状态迁移系统及接收条件构成最终的确定性自动机。本发明可以降低状态复杂度，提升计算效率，简化实现流程，提高工程可行性。