VC-dimensions of nondeterministic finite automata for words of equal length

Bjørn Kjos-Hanssen, Clyde James Felix, Sun Young Kim +2

Let $NF{A}_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 leng…