ПРОГРАММА ЭКЗАМЕНА . Часть 1

1. Конечные автоматы

   1. Регулярные выражения и регулярные множества.
   2. Определение недетерминированного конечного автомата. Язык, задаваемый конечнымм автоматом.
   3. Теорема о задании детерминированным конечным автоматом языка, задаваемого недетерминированным конечным автоматом.
   4. Теорема о задании недерминированными конечными автоматами регулярных языков.
   5. Системы линейных уравнений с регулярными коэффициентами.
   6. Теорема о регулярности решения системы линейных уравнений с регулярными коэффициентами.
   7. Теорема о регулярности языка, задаваемого конечным автоматом.
   8. Теорема о разрастании для регулярных языков.
   9. Примеры нерегулярных языков.
   10. Замкнутость класса регулярных языков относительно теоретико-множественных операций.
   11. Замкнутость класса регулярных языков относительно гомоморфизмов и прообразов при гомоморфизмах.
   12. Замкнутость класса регулярных языков относительно взятия начал, концов и подслов.

2. Грамматики

   1. Кс-грамматики и кс-языки.
   2. Теорема о том, что язык правильно расставленных скобок контекстно свободен.
   3. Теорема о том, что каждый регулярный язык контекстно свободен.
   4. Лемма о выводимости из конкатенации.
   5. Теорема о нахождении пустых нетерминалов.
   6. Теорема о нахождении недостижимых нетерминалов.
   7. Теорема о построении эквивалентной кс-грамматики без бесполезных нетерминалов.
   8. Теорема о построении эквивалентной кс-грамматики без правил с пустой правой частью.
   9. Теорема о построении эквивалентной кс-грамматики без цепных правил.
   10. Теорема о построении эквивалентной приведённой кс-грамматики.
   11. Теорема о замене нетерминала на все его следствия.
   12. Теорема о нормальной форме Хомского.
   13. Теорема об устранении левой рекурсии.
   14. Теорема о нормальной форме Грейбах в слабой форме.
   15. Теорема о нормальной форме Грейбах в сильной форме.
   16. Автоматы с магазинной памятью.
   17. Теорема об эквивалентности различных определений задания языка для автоматов с магазинной памятью.
   18. Теорема о задании кс-языков автоматами с магазинной памятью.
   19. Теорема о том, что каждый язык, задаваемый автоматом с магазинной памятью, контекстно свободен.
   20. Деревья выводов.
   21. Теорема о задании выводимого слова деревом вывода.
   22. Теорема о выводимости слов, задаваемых деревьями выводов.
   23. Теорема о длине пути в дереве вывода длинного слова.
   24. Теорема Огдена.
   25. Примеры языков, не являющихся контекстно свободными.
   26. Теоремы замкнутости для кс-языков.
   27. Теорема о незамкнутости класса кс-языков относительно пересечений и дополнений.

3. Программы

   1. Определение структурированной программы. Работа программы на состоянии.
   2. Функции, вычисляемые структурированной программой.
   3. Определение програмы с метками. Работа программы на состоянии.
   4. Совпадение классов функций, вычислимых структурированными программами и программами с метками.
   5. Теорема о том, что каждая вычислимая функция вычисляется структурированной программой специального вида.
   6. Частично рекурсивные функции.
   7. Рекурсивность основных арифметических функций.
   8. Теоремы об ограниченных суммировании и перемножении.
   9. Теорема о разборе случаев.
   10. Теорема о программной вычислимости каждой частично рекурсивной функции.
   11. Теорема о рекурсивности функций, вычисляемых программой без циклов в переменных.
   12. Теорема о частичной рекурсивности функций, вычисляемой программой в переменных.
   13. Теорема о частичной рекурсивности программно вычислимых функций.
   14. Неразрешимые проблемы. Неразрешимость проблемы остановки на своём номере. Неразрешимость проблемы остановки на нуле. Неразрешимость проблемы эквивалентности.

4. Машины Тьюринга

   1. Определение машины Тьюринга. Работа машины Тьюринга на слове Поста и на ленте.
   2. Основные машины Тьюринга. Доказательство их существования.
   3. Операции над машинами Тьюринга.
   4. Определение моделируемости работы структурированной программы машиной Тьюринга.
   5. Теорема о том, что работа каждой структурированной программы моделируется некоторой машиной Тьюринга.
   6. Определение вычислимости арифметической функции машиной Тьюринга.
   7. Теорема о том, что каждая частично рекурсивная функция вычисляется некоторой машиной Тьюринга.
   8. Нумерация машин Тьюринга и слов Поста.
   9. Теорема о номере следующего слова Поста.
   10. Теорема о частичной рекурсивности каждой функции, вычисляемой машиной ТЬюринга.
   11. Универсальные функции. Теорема о несуществовании рекурсивной функции, универсальной для класса всех одноместных рекурсивных функций.
   12. Теорема о существовании частично рекурсивной функции, универсальной для класса всех частично рекурсивных функций с заданным числом аргументов.
   13. Теорема о существовании одноместной частично рекурсивной функции, область определения которой не является рекурсивной и которая равна 0, если она определена.

5. Ассоциативные исчисления

   1. Полусистемы Туэ. Построение полусистемы Туэ по машине Тьюринга. Теорема о выводимости слов Поста в построенной по машине Тьюринга полусистеме Туэ.
   2. Полугруппы, заданные образующими и определяющими соотношениями. Система канонических представителей.
   3. Построение ассоциативного исчисления по полусистеме Туэ. Теорема о выводимости заключительного слова Поста в ассоциативном исчислении, построенном по полусистеме Туэ.
   4. Неразрешимоть проблемы равенства в теории полугрупп.