  We present a new approach to formal language theory using Kolmogorov
complexity. The main results presented here are an alternative for pumping
lemma(s), a new characterization for regular languages, and a new method to
separate deterministic context-free languages and nondeterministic context-free
languages. The use of the new `incompressibility arguments' is illustrated by
many examples. The approach is also successful at the high end of the Chomsky
hierarchy since one can quantify nonrecursiveness in terms of Kolmogorov
complexity. (This is a preliminary uncorrected version. The final version is
the one published in SIAM J. Comput., 24:2(1995), 398-410.)

Computational Complexity