Лекция 8. Конечные автоматы и вычисления с константной памятью.
Обзорный курс по теоретической информатике


Что: Лекция
Когда: Четверг, 27 октября 2016, 18:30–19:50
Где: ПОМИ РАН

Описание

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