Детерминированные и недетерминированные конечные автоматы. Автоматы и регулярные выражения. Лемма о накачке. Автоматные языки и классы эквивалентности. DSpace[1] совпадает с множеством автоматных языков. Пример языка, который не является автоматным, но решается с использованием O(loglogn) памяти. DSpace[o(loglogn)]=DSpace[1].