13. Конечные преобразователи
Конечные преобразователи — это модели систем, которые работают неопределённо долгое время, в каждый момент получают определённые входные сигналы и выдают некоторые результаты. Пример простого конечного преобразователя — преобразование двоичной записи числа N в двоичную запись числа N + 1, при этом двоичная запись числа подаётся с конца. Более сложным примером использования автоматических преобразователей является синтез речи — отображение последовательности букв в последовательность фонем. Как правило, в задаче построения конечного преобразователя исходными данными является «обучающее множество»: пары последовательностей символов, которые состоят из входной последовательности и соответствующей ей выходной последовательности. Задача состоит в построении конечного преобразователя, который содержит заданное число состояний и корректно преобразует последовательности, входящие в обучающее множество. Конечные автоматы-преобразователи (трансдьюсеры) находят применение во многих областях информатики, таких как вычислительная лингвистика и обработка текстов, биоинформатика, проектирование реагирующих и распределённых систем. 00:05 Введение и цель лекции 01:03 Лемма 6 03:46 Индукция 05:59 Переход 13:05 Второй случай 16:29 Заключение 18:47 Вывод и правила 20:52 Редиот и правила 22:37 Доказательство и автомат 27:01 Введение в конечные преобразователи 32:57 Определение конечного преобразователя 36:32 Конфигурация и выводимость 38:50 Введение в конечные преобразования 42:03 Примеры конечных преобразований 46:31 Примеры конечных преобразований 48:13 Гомоморфизм и примеры 52:17 Теорема об ограничении конечного преобразования 01:00:14 Введение в доказательство 01:00:50 Параметры переходов 01:03:00 База индукции 01:04:07 Переход 01:05:28 Первый вариант перехода 01:08:35 Второй вариант перехода 01:11:03 Заключение
Конечные преобразователи — это модели систем, которые работают неопределённо долгое время, в каждый момент получают определённые входные сигналы и выдают некоторые результаты. Пример простого конечного преобразователя — преобразование двоичной записи числа N в двоичную запись числа N + 1, при этом двоичная запись числа подаётся с конца. Более сложным примером использования автоматических преобразователей является синтез речи — отображение последовательности букв в последовательность фонем. Как правило, в задаче построения конечного преобразователя исходными данными является «обучающее множество»: пары последовательностей символов, которые состоят из входной последовательности и соответствующей ей выходной последовательности. Задача состоит в построении конечного преобразователя, который содержит заданное число состояний и корректно преобразует последовательности, входящие в обучающее множество. Конечные автоматы-преобразователи (трансдьюсеры) находят применение во многих областях информатики, таких как вычислительная лингвистика и обработка текстов, биоинформатика, проектирование реагирующих и распределённых систем. 00:05 Введение и цель лекции 01:03 Лемма 6 03:46 Индукция 05:59 Переход 13:05 Второй случай 16:29 Заключение 18:47 Вывод и правила 20:52 Редиот и правила 22:37 Доказательство и автомат 27:01 Введение в конечные преобразователи 32:57 Определение конечного преобразователя 36:32 Конфигурация и выводимость 38:50 Введение в конечные преобразования 42:03 Примеры конечных преобразований 46:31 Примеры конечных преобразований 48:13 Гомоморфизм и примеры 52:17 Теорема об ограничении конечного преобразования 01:00:14 Введение в доказательство 01:00:50 Параметры переходов 01:03:00 База индукции 01:04:07 Переход 01:05:28 Первый вариант перехода 01:08:35 Второй вариант перехода 01:11:03 Заключение