Finite state automaton construction through regular expression hashing
Rayner Johannes Lodewikus Coetser · UpSpace Institutional Repository (University of Pretoria) · 2009
I would like to thank my parents and sister for their support while writing this dissertation. I would also like to thank my supervisors for their valuable input, and Loek Cleophas, who read my dissertation and article. In this study, the regular expressions forming abstract states in Brzozowski’s algorithm are not remapped to sequential state transition table addresses as would be the case in the classical approach, but are hashed to integers. Two regular expressions that are hashed to the same hash code are assigned the same integer address in the state transition table, reducing the number of states in the automaton. This reduction does not necessarily lead to the construction of a minimal automa-ton: no restrictions are placed on the hash function hashing two regular expressions to the same code. Depending on the quality of the hash function, a super-automaton, previously referred to as an approximate automaton, or an exact automaton can be constructed. When two regular expressions are hashed to the same state, and they do not represent the same regular language, a super-automaton is constructed.