14 Доказательство инварианта Теорема Нива

Теорема Нива в теории формальных языков утверждает, что всякое конечное преобразование представляется в виде τ = ψ−1 ◦ idr ◦ ϕ, где idR — тождественное преобразование, ограниченное на регулярный язык R, ϕ, ψ — неудлинняющие гомоморфизмы 00:05 Введение и цели лекции 01:02 Основные факты о конечных преобразованиях 01:41 Переходы в автомате 03:46 Доказательство леммы 06:16 Примеры переходов 09:05 Объединение переходов 12:45 Второй случай 16:33 Завершение доказательства 20:00 Заключение 20:49 Композиция конечных преобразований 21:43 Доказательство композиции 26:01 Построение декартова произведения 27:10 Определение переходов 30:16 Доказательство теоремы 33:18 Пример доказательства 41:15 Заключение 42:25 База 43:52 Переход 45:12 Варианты переходов 47:01 Доказательство перехода 53:24 Композиция конечных преобразований 56:21 Разложение конечного преобразования 01:00:06 Гомоморфизмы и не удлиняющие гомоморфизмы 01:02:50 Теорема Нева 01:05:11 Введение в конечные преобразования 01:07:05 Автомат на дельта 01:10:10 Гомоморфизм и регулярные выражения 01:12:05 Ограничения на регулярные языки 01:15:05 Регулярность конечного преобразования 01:17:02 Доказательство регулярности 01:25:13 Заключение и упражнения