  In this article we undertake a study of extension complexity from the
perspective of formal languages. We define a natural way to associate a family
of polytopes with binary languages. This allows us to define the notion of
extension complexity of formal languages. We prove several closure properties
of languages admitting compact extended formulations. Furthermore, we give a
sufficient machine characterization of compact languages. We demonstrate the
utility of this machine characterization by obtaining upper bounds for
polytopes for problems in nondeterministic logspace; lower bounds in streaming
models; and upper bounds on extension complexities of several polytopes.
