If a language is not regular, it requires a machine with at least Ω(log log n) space to recognize (where n is the input size).
Dacă un limbaj nu este regulat, este nevoie de o mașină cu spațiu de cel puțin O(log log n) pentru a-l recunoaște (unde n este lungimea intrării).