One of the most useful properties of regular and context-free languages is the well-known pumping lemmas of Bar-Hillel, Perles, Shamir [1] in 1961. In this work, we consider their most natural generalization for languages beyond regular and context-free languages. In fact, we prove that languages recognized by one-way nondeterministic depth-k storage automata (or k-sna’s) satisfy such a generalization for every positive integer k. As a direct application of this generalized pumping lemma, we demonstrate a separation of the complexity classes of languages recognized by k-sna’s for different positive integers k. This result instantly implies that those complexity classes form truly infinite hierarchies.