Езици, автомати, изчислимост

0. Увод
1.Крайни автомати. Регулярни операции.
2.Недетерминирани крайни автомати. Представяне на всеки недетерминиран автомат с детерминиран.
3.Затвореност относно регулярните операции.
4.Теорема на Клини.
5.Лема за покачването. Примери за регулярни и нерегулярни езици.
6.Минимизация на състоянията. Теорема на Майхил – Нероуд.
7.Контекстно-свободни граматики. Дървета за синтактичен анализ.
8.Стекови автомати.
9.Връзка между стековите автомати и контекстно-свободните граматики.
10.Свойства на затвореност. Лема на покачването. Примери за езици, които не са котекстно-свободни.
11.Машини на Тюринг. Изчислимост с машини на Тюринг.
12.Разрешими и полуразрешими езици.
13.Многолентови машини на Тюринг.
14.Недетерминирани машини на Тюринг.
15.Тезис на Чърч – Тюринг. Граматики от общ тип.
16.Примитивно рекурсивни и частично рекурсивни функции.
17.Универсални машини на Тюринг.
18.Неразрешими проблеми. Теорема на Райс-Успенски.
19.Класовете P и NP. Примери.
20.NP-пълнота. Някои NP-пълни задачи.

Упражнения, контролни, изпит.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License