Results on the Average State and Transition Complexity of Finite Automata Accepting Finite Languages (Extended Abstract).
Hermann Gruber, Markus Holzer · 2006
We investigate the average-case state and transition complexity of deterministic and nondeterministic finite automata, when choosing a finite language of given maximum word length n uniformly at random. The case where all words are of equal length is also taken into account. It is shown that almost all deterministic finite automata accepting finite languages over a binary input alphabet have state complexity Θ ( 2n n). Moreover, we develop a framework that allows us to investigate the average-case complexity of operations like union, intersection, complementation, and reversal on finite languages. Nondeterministic finite automata are shown to perform better than deterministic ones, namely their state complexity is in Θ ( √ 2n) on the average. Interestingly, in both cases the aforementioned bounds are asymptotically like in the worst case. However, the nondeterministic transition complexity is shown to be again Θ ( 2n n). The case of unary finite languages is also considered. 1