An investigation is conducted of the Vapnik-Chervonenkis dimensions (VC-dimensions) of finite automata having k letters and n states. It is shown for a fixed positive integer k (≥2), that (1) the VC-dimension of DFAk(n):= {L∈{1, 2, …, k}* : some deterministic finite automaton with at most n states accepts L} is n + log2 n - O(log logn) for k = 1 and (k - 1 + 0(1))n log2 n for k≥2, and (2) the VC-dimension of CDFAk(n):= {L∈DFAk(n) : L is commutative} is n + o(n).
展开▼
