Chrobak Normal Form Revisited, with Applications

摘要

It is well known that any nondeterministic finite automata over a unary alphabet can be represented in a certain normal form called the Chrobak normal form [1]. We present a very simple conversion procedure working in O(n~3) time. Then we extend the algorithm to improve two trade-offs concerning conversions between different representations of unary regular languages. Given an n-state NFA, we are able to find a regular expression of size O(n~2/log~2 n) describing the same language (which improves the previously known O(n~2) size bound [8]) and a context-free grammar in Chomsky normal form with O(n log n~(1/2)) nonterminals (which improves the previously known O(n~(2/3)) bound [3]).