Learning a class of regular languages in the probably approximately correct learnability framework of Valiant

Results are given, relating to the probably approximately correct (M.A. Harrison, 1978) learning of a class of regular languages called terminal distinguishable regular languages. The authors prove that the VC-dimension of this concept class is infinite. However, when further restriction is imposed on the length and the structure of strings this class is found to have finite VC-dimension that grows linearly with l. This motivates the design and analysis of a highly space-efficient learning algorithm for the class, which is then presented.