На главную страницу НМУ

Анна Оверчук

Формальные языки

Цель данного курса: понять, что такое вычисление с алгебраической точки зрения. Самой естественной моделью вычислений в теоретической информатике является конечный автомат, который, как известно, распознает регулярные языки. В первой части курса мы опишем регулярные языки используя их внутреннюю алгебраическую структуру и обобщим эти понятия на произвольные формальные языки; а во второй части с помощью внутреннего описания вычисления введем на них топологию и обобщим классические теоремы универсальной алгебры (многообразия алгебраических структур).

Программа курса

  1. Слова, языки, вычисления

  2. Рациональные и распознаваемые подмножества моноида

  3. Синтаксический моноид, теорема Клини, теорема Майхила-Нероуда

  4. Регулярность и произвольные алгебры Клини

  5. Моноиды и формальная логика, теорема Шюценберже

  6. Топология, профинитные слова

  7. Многообразия, теорема Биркгофа, теорема Рейтермана