Abstract:
"We study the subset construction that transforms nondeterministic finite automata (NFA) to deterministic finite automata (DFA). It is well known that given a n-state NFA, the subset construction algorithm produces a 2 n -state DFA in the worst case. We provide regular languages such that given n, k (k > 1 and n > k), the minimal NFA recognizing the language has n states and the minimal DFA recognizing these languages has (k + 1)n−(k + 1)2 + 2 states. Futhermore, we show that for every n = k + m and p ∈ N + (k, m > 1 and m = 2 k+1−pk−2p p−1 ) there exists a regular language Ln, such that the minimal NFA recognizing the language has n states and the minimal DFA recognizing the language has p · n states. In addition, for every k > 1, we provide a regular language such that the minimal NFA recognizing the language has n-states, and the minimal DFA recognizing the language has asymptotically n k states. Importantly, the minimal NFA has O( n 2 log2n ) number of transitions, which is fewer than the known results in literature [8, 9]. We also investigate the question of the complementation of NFA. We provide regular languages such that given n, k (k > 1 and n > k), the NFA recognizing these languages need n states and the minimal NFA recognizing their complement has (k + 1)n − (k + 1)2 + 2 states. Finally we show that for given n, k > 1, there exists an O(n)-state NFA A such that the minimal NFA recognizing the complement of L(A) has between O(n k−1 ) and O(n 2k ) states. Importantly, the constructed NFA have a small number of transitions, i.e., between O(n) or O(n 2/log2(n)). These are better than the comparable results in literature [7, 9]. Furthermore, we study properties of random automata. We consruct random automata by assigning transitions between any ordered pair of states with a fixed probability. We examine with which probability a random automaton is deterministic, which languages are accepted by most automata,
and the probability of a random automaton having exponential blow-up upon determinization."