Вопросы

Отношения. Свойства отношений. Отношение эквивалентности. Отношение порядка.

Языки и операции над ними

Системы текстовых замен (СТЗ). Отношение выводимости в СТЗ. Определение языков с помощью СТЗ

Нормальные алгоритмы Маркова (НАМ). Отношение выводимости в НАМ.

Нормальные системы Поста (НСП). Отношение выводимости в НСП.

Аналитические и порождающие грамматики. Определение языков с помощью грамматик.

Классификация грамматик по Хомскому. Доказательство того, что конечные языки принадлежат к любому из классов языков.

Конечные детерминированные автоматы (КДА). Определение языков с помощью КДА.

Конечные недетерминированные автоматы (НКА). Определение языков с помощью НКА.

Автоматы с магазинной памятью (МПА). Определение языков с помощью МПА.

Линейные ограниченные автоматы (ЛОА). Определение языков с помощью ЛОА.

Машины Тьюринга (МТ). Определение языков с помощью МТ.

Регулярные множества и регулярные выражения.

Теорема 1 о существовании двойственной грамматики.

Теорема 2 о существовании эквивалентной порождающей грамматики без терминалов в левых частях правил.

Теорема 3 о замкнутости классов языков относительно регулярных операций: доказательство замкнутости класса языков типа 0.

Теорема 3 о замкнутости классов языков относительно регулярных операций: доказательство замкнутости класса языков типа 1.

Теорема 3 о замкнутости классов языков относительно регулярных операций: доказательство замкнутости класса языков типа 2.

Теорема 3 о замкнутости классов языков относительно регулярных операций: доказательство замкнутости класса языков типа 3.

Теорема 4 о замкнутости классов языков типа 0-2 относительно операции зеркального отражения.

Теорема 5 о замкнутости классов языков типа 0 и 2 относительно подстановки.

Теорема 6 о замкнутости класса языков типа 0 относительно операции пересечения.

Теорема 7 об эквивалентности классов языков определенных автоматами и грамматиками типа 3: доказательство в части построения грамматики по автомату.

Теорема 7 об эквивалентности классов языков определенных автоматами и грамматиками типа 3: доказательство в части конечного детерминированного автомата по грамматике.

Следствие теоремы 7 о замкнутости класса языков типа 3 относительно дополнения ит пересечения.

Теорема 8 о том, что любой язык, определяемый машиной Тьюринга является языком типа 0.

Теорема 9 о регулярности языков типа 3.

Теорема 10 о замкнутости класса языков типа 3 относительно операций зеркального отражения, подстановки и гомоморфизма.

Теорема 11 о праволинейности языков типа 3.

Теорема 12 о несамовставленности языков типа 3.

Теорема 14: Лемма о накачке для регулярных языков.

Теорема 15 об однозначности языков типа 3.

Теорема 16 о возможности устранения ε-правил из грамматики типа 2.

Теорема 17 о возможности устранения цепных правил из грамматики типа 2.

Теорема 18 о возможности приведения грамматики типа 2 в нормальную форму Хомского.

Теорема 19: лемма о накачке для КС-языков.