Лекция 8. Конечные автоматы и вычисления с константной памятью.

Четверг, 27 октября 2016, 18:30–19:50
ПОМИ РАН

Описание

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