Практика языка C (МФТИ, 2023-2024). Семинар 5.2. Регулярные выражения и автоматы.

Практические занятия по языку C на первом курсе МФТИ. Кафедра информатики.

На этом занятии мы погрузимся в более интересную обработку строковой информации. Вы познакомимся с понятиями конечного автомата и регулярного выражения, поиграем с утилитой grep, научимся писать наши собственные регулярные выражения на C и даже используем их для условно-практических задач (скажем распознавания email в тексте).

Семинарист: Константин Владимиров.
Дата: 12 февраля 2024 года.
Съёмка: Марк Гончаров.
Звук: Юлий Тарасов.

Предыдущий семинар:    • Практика языка C (МФТИ, 2023-2024). С...  
Следующий семинар:    • Практика языка C (МФТИ, 2023-2024). С...  

Слайды к занятиям: https://github.com/tilir/c-graduate/t...
Примеры кода: https://github.com/tilir/c-graduate
Задачник: https://contest.yandex.ru/contest/664...

Timeline
00:00 Формальные языки
06:30 Конечные автоматы
13:30 Виртуозное использование switch
17:44 Построение простого автомата
25:30 Регулярные выражения, POSIX regex и утилита grep
32:00 Регулярные выражения на языке C
38:10 Недетерминированные автоматы
42:42 Время решать задачи
45:10 Пределы регулярности
50:35 Префиксная функция и поиск подстроки
01:00:05 Алгоритм Кнута-Морриса-Прата и префикс-функция как автомат
01:05:50 Ещё одна идея для написания автоматов
01:18:30 Продолжаем ревью и завершение

Errata
пока пусто