Before revision:  In this hierarchy, regular languages are sorted according to the new fundamental measure of NFA complexity p. Our main contributions are the following: (i) we show that the hierarchy is strict and does not collapse, (ii) we provide (exponential  ) upper and lower bounds relating the minimum widths of equivalent NFAs and DFAs , and (iii) we characterize DFAs of minimum p for a given \mathcal L via a co-lexicographic variant of the Myhill-Nerode theorem.
After revision:  We show that the hierarchy is strict and does not collapse, (ii) we provide (exponential ) upper and lower bounds relating the minimum widths of equivalent NFAs and DFAs , and (iii) we characterize DFAs of minimum p for a given \mathcal L via a co-lexicographic variant of the Myhill-Nerode theorem.