Лемма о разрастании формулируется следующим образом. Если дан регулярный язык и достаточно длинная цепочка символов, принадлежащая этому языку, то в ней можно найти непустую подцепочку, которую можно повторить сколь угодно много раз, и все полученные таким образом цепочки также будут принадлежать рассматриваемому регулярному языку.

Формально лемма записывается так. Если дан язык L, то $ константа p>0, такая, что если aÎL и ½a½³p, то цепочку a можно записать в виде a=dbg, где 0<½b½£p, и тогда a¢=dbig, a¢ÎL "i³0.