VC-dimensions of nondeterministic finite automata for words of equal
  length
  Let $NFA_b(q)$ denote the set of languages accepted by nondeterministic
finite automata with $q$ states over an alphabet with $b$ letters. Let $B_n$
denote the set of words of length $n$. We give a quadratic lower bound on the
VC dimension of \[
  NFA_2(q)\cap B_n = \{L\cap B_n \mid L \in NFA_2(q)\} \] as a function of $q$.
  Next, the work of Gruber and Holzer (2007) gives an upper bound for the
nondeterministic state complexity of finite languages contained in $B_n$, which
we strengthen using our methods.
  Finally, we give some theoretical and experimental results on the dependence
on $n$ of the VC dimension and testing dimension of $NFA_2(q)\cap B_n$.
