План по ЕАИ ( зима 2018 г. )
- Увод. Крайни детерминирани автомати. Примери. Конструкции за сечение, обединение, разлика
- Крайни недетерминирани автомати. Еквивалентност с КДА. Пример за експоненициално покачване на броя на състоянията. Контрукция за конкатенация на автоматни езици
- Контрукция за звезда на Клини на автоматни езици. Регулярни изрази и езици. Теорема на Клини
- Лема за покачването. Примери. Релация на Майхил-Нероуд
- Теорема на Майхил-Нероуд. Метод на Бжозовски
- Изоморфни автомати. Алгоритъм за минимизация
- Граматики. Регулярни граматики. Извод в граматика
- Дървета на извод. Лема за покачването за безконтекстни езици
- -- няма лекция --
- Опростяване на граматики
- Нормална форма на Чомски. CYK алгоритъм
- Стекови автомати. Теорема за еквивалентност с безконтекстни граматики
- Детерминистични машини на Тюринг. Разрешими езици. Примери. Многолентови детерминистични машини на Тюринг
- Недетерминистични машини на Тюринг
- Кодиране на машини на Тюринг. Примери за неразрешими и неполуразрешими езици. Теорема на Райс