Prague Stringology Conference 2016
Mwawi Msiska and Lynette van Zijl
Interpreting the Subset Construction Using Finite Sublanguages
| Abstract: |
| We present a language-based approach to the well-known problem of the conversion between finite automaton (FA) types. We base our approach on the existence, for any FA, of a finite subset of the language of the FA, which we call the finite exhaustive language (FEL). An FA uses all its reachable transitions after computing all strings in its FEL. We convert the FA by summarizing its computations on strings from the FEL of its equivalent FA. We illustrate our approach using the well known nondeterministic finite automaton (NFA) to deterministic finite automaton (DFA) conversion. We describe a method to calculate the FEL of the DFA through graph traversals of the NFA, without first converting the NFA into a DFA. Using the FEL, we construct a DFA that has neither dead nor unreachable states. For an n-state NFA, we show that O(e√ n log n) is an upper bound on the length of strings in the FEL of its equivalent DFA. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |