Дискретная математика | 3A. Автоматы Милли и Мура, RegExp, AX

Описание

Продолжим рассматривать конечные автоматы (КА), их различные варианты. Но, чтобы это сделать, дадит сначала их формальное определение. Вспомним, что такое регулярные выражения (RegExp). Оказывается, задать КА, распознающий определённые слова, и описать их регулярным выражением - задачи эквивалентные.

Иные слова не так просты, как кажется. Слова обладают естественной операцией умножения - контакенацией. Поэтому можно изучать структуру сомножителей слов. Этим занимается раздел "combinatorics on words".

Можно просматривать на скорости 1.25

0:00 Повторение 1 серии. Числовые последовательности. Удивительное совпадение
9:40 Повторение 2 серии. Автоматы.
14:05 Формальное определение автоматов
15:45 Вопрос про обобщение автоматов*
19:00 Автомат с выводом
21:30 Заяц. Автомат для Туэ-Морса
28:10 Автомат Мура
33:25 Автомат Милли
39:00 Операция сдвига
49:05 Число дописываем нулями слева. Самый левый бит при сдвиге теряется.
52:00 Вспоминаем ЯП и ещё одну унарную операцию
59:30 Регулярные выражения
1:06:50 Грамматика? Не скажу что такое
1:09:00 Combinatorics of words, axaxa
1:22:05 Эйве
1:23:35 Правила для последовательности Туэ-Морса, символьной последовательности Фибоначчи.

[*] Обобщением КА может быть автомат с магазинной памятью, Pushdown Automaton, https://en.wikipedia.org/wiki/Pushdown_automaton. С другой стороны, мы можем ограничить возможности Машины Тьюринга вплоть до того, что определение станет эквивалентным КА: ограничим головку операцией чтения и на каждом шаге будем её смещать вправо.