{'fraction_non_alphanumeric': 0.02821316614420063, 'fraction_numerical': 0.003918495297805642, 'mean_word_length': 4.88479262672811, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Computational Complexity of NFA Minimization for Finite and Unary Languages

We investigate the computational complexity of the nondeterministic finite automaton (NFA) minimization problem for finite and unary regular languages, if the input is specified by a deterministic finite state machine. While the general case of this problem is PSPACEcomplete [13], it becomes theoretically easier when restricted to the aforementioned language families. It is easy to see that in both cases, an upper bound is ΣP2 , the second level of the Polynomial Hierarchy. Concerning a respective lower bound, we show that the minimization problem for NFAs accepting finite languages is hard for the complexity class DP, which includes both NP and coNP, and is a subset of ΣP2 . Moreover, we show that the corresponding problem for unary regular languages in general, i.e., not limited to the cyclic case, can be approximated in polynomial time within a performance ratio of O( √ n), where n is the number of states of the given deterministic finite state machine. This generalizes a result obtained recently for cyclic unary languages [6]. We also show that one cannot approximate the unary NFA minimization problem with o(n), if the input is an NFA, which is an optimal bound, unless P = NP.