Si un lenguaje no es regular requiere una máquina con al menos una complejidad de Ω(log log n) (donde n es el tamaño de la entrada).