The previously proposed approaches have two main drawbacks. Finally, the dynamic minimization solution proposed by Carrasco and Forcada keeps an automaton minimal when insertions or deletions are performed. Another incremental determinization algorithm for general finite automata called ISC is presented in. Daciuk proposed an incremental algorithm for minimizing finite state automata that allows the minimization to be merged with the construction in a single step by adding new strings one by one and minimizing the resulting automaton on-the-fly. Recently, studies on automaton minimization algorithms have mainly focused on incremental construction and dynamic DFA minimization, which is the fourth classification. In the third category, Brzozowski’s algorithm reverses and trims the automaton twice to obtain the minimal DFA. Almeida and Zeitoun extended it to automata whose nontrivial strongly connected components are cycles. The disadvantage of Revuz’s algorithm is that it is constrained to acyclic automata. The most famous algorithm of this type is Revuz’s algorithm, which has a linear time complexity. The second type of minimization algorithm uses a sequence of merging states. However, it leads to a quadratic worst-case time complexity. Moore’s algorithm is much simpler than Hopcroft’s algorithm.
Hopcroft’s algorithm has recently been extended to handle incomplete DFAs, and has now been re-described many times to make it easier to understand. Several authors have proven the tightness of the upper bound of this complexity for different families of automata. At present, Hopcroft’s algorithm is the most efficient known algorithm and has a worst-case time of O( n log n). Hopcroft’s and Moore’s algorithms also fall into this category. A typical method is mentioned in, and has time complexity O( n 2).
#Construct a deterministic finite automaton series#
The first category uses a series of refinements of a partition on the state set. Many algorithms can be used to minimize a DFA, and these can be classified into four categories.
The minimization of a DFA is beneficial not only for practical applications, but also mathematical problems in theory. This means that the minimal DFA is unique, and has the least number of states needed to recognize a language represented by regular expressions or regular grammar. It has been proven theoretically that a DFA has a unique minimal formalization, but only up to isomorphism. In this paper, we focus on the minimization problem without considering the conversion from regular expressions or regular grammar to DFA. To save memory space, the minimization of a DFA is indispensable in practical applications. Regular expressions are usually used to describe engineering requirements in practice, and they can be converted into a DFA by a sequence of operations. DFAs are used widely because they have predictable and acceptable memory bandwidth requirements. Finite automata mainly have two alternative implementations: nondeterministic finite automatons (NFAs) and deterministic finite automatons (DFAs). Finite automata is widely used in areas such as text processing, compilation, pattern matching, network intrusion detection and protection, image analysis and spatial dynamics. Regular grammar and regular expressions generate regular languages, and finite automata is a computation model of speech recognition for regular languages. A comparison to Hopcroft’s algorithm demonstrates experimentally that the algorithm runs faster than traditional algorithms.įinite automata, regular grammar, and regular expressions are three dissimilar representations for regular languages. Overall, the proposal has three advantages: lower time complexity, greater generality, and scalability. The proposed algorithm can be applied not only to the minimization of acyclic automata or simple cyclic automata, but also to automata with high topological complexity. This method achieves greater generality than previous methods because building the backward depth information is independent of the topological complexity of the DFA. Few states need to be refined by the hash table, because most states have been partitioned by the backward depth information in the coarse partition. The minimization algorithm has a lower time complexity O( n) than a naive comparison of transitions O( n 2). In the second phase, the state set is refined using a hash table. In the first phase, the backward depth information is built, and the state set of the DFA is partitioned into many blocks. A minimization algorithm is presented in this paper that consists of two main phases. Obtaining a minimal automaton is a fundamental issue in the theory and practical implementation of deterministic finite automatons (DFAs).
0 kommentar(er)
