VC-DIMENSIONS OF FINITE AUTOMATA AND COMMUTATIVE FINITE AUTOMATA WITHK-LETTERS AND N-STATES

An investigation is conducted of the Vapnik-Chervonenkis dimensions (V C-dimensions) of finite automata having k letters and n states. It is shown for a fixed positive integer k(greater than or equal to 2) that (1) the VC-dimension of DFA(k)(n) := {L subset of(1,2,..., k} : some deterministic finite automaton with at most n states accepts L} is n log(2) n - O(log log n) for k = 1 and (k - 1 + o(1))n log(2) n for k greater than or equal to 2, and (2) the VC-dimension of CDFA(k)(n) := {L epsilon DFA(k)-(n) : L is commutative} is o(n).s n + o(n).