Dissertation > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > General issues > Theories, methods > Automata Theory

A class of non - deterministic finite automata minimization and complexity

Author LiHanFang
Tutor XuDaoYun
School Guizhou University
Course Basic mathematics
Keywords Connection type finite automata Equivalence relation Indistinguishable state Time complexity Tree graph partitioning method Critical condition
CLC TP301.1
Type Master's thesis
Year 2008
Downloads 64
Quotes 0
Download Dissertation

In this paper, the theory of automata mainly two aspects: the complexity of automata minimization and minimization of the time . Defined on the equivalence relations in the set of states of the automaton , the introduction of the equivalence class , would be equivalent to state merged into one state , generating a smaller number of new state automaton . Identify the language of the new generation of automatic machine with the automatic machine unchanged , meaning that they are equivalent . This is the idea of the tree graph partitioning method . Tree graph partitioning method can be deterministic finite automata minimization . The focus of this paper is to construct a class of non - deterministic finite automata, the connection type finite automata . Kind of finite automata by two deterministic finite automata are connected . The use of two deterministic finite automata equivalence relation on the set of states can be constructed connection type equivalence relation on the set of states of finite automata . Such non- deterministic finite automata can also use the tree graph partitioning method to minimization . Can also get the status of the connection and then minimization of automata is not greater than the number of states of the automata minimization and then connect . Non- deterministic finite automata the situation is more complicated . Often relatively large finite automata equivalent states , but a two or several states to merge does not change their language . In this paper, a non-deterministic finite automata state merger conditions . Find a non-deterministic finite automata minimization state critical condition . The automata minimization time complexity of the effective authentication minimization algorithm is valid . , Completed in polynomial time that the algorithm is effective . Deterministic finite automata finite automaton the tree graph partitioning method minimization and connection type , they all can be completed in the state cubic time . The end of this article gives a non- deterministic finite automata minimization algorithm .

Related Dissertations
More Dissertations