4 МПДКА Праволинейные грамматики

Праволинейная грамматика — это грамматика, в которой все правила имеют вид A→a|aB, где a — терминальные символы, а A,B — нетерминальные. Такие грамматики определяют в точности все регулярные языки и поэтому эквивалентны конечным автоматам и регулярным выражениям. 00:05 Введение в минимальные полные детерминированные конечные автоматы 00:51 Отношения эквивалентности по языку и состоянию 02:14 Доказательства и леммы 05:18 Построение МПДКА 08:05 Согласованность переходов и завершающего состояния 14:41 Доказательство равенства языков 18:55 Переходы и классы эквивалентности 21:33 Доказательство попарной неэквивалентности состояний 27:04 Минимальный ПДК 35:16 Оценка количества состояний 38:39 Изоморфизм ПДК 40:35 Введение в изоморфизм автоматов 42:24 Теорема о единственности изоморфизма 46:00 Построение изоморфизма для автоматов 50:10 Проверка согласованности переходов 57:00 Доказательство инъективности изоморфизма 01:02:12 Эквивалентность состояний 01:04:38 Согласованность переходов 01:08:19 Проверка изоморфизма автоматов 01:10:50 Построение минимального ПДК 01:13:27 Доказательство минимального автомата

Видео 4 МПДКА Праволинейные грамматики автора Сталинский Букварь