Математическая теория формальных языков
Проблема эквивалентности детерминированных МП-автоматов
Теорема 15.7.1.
Существует алгоритм, позволяющий по произвольным двум детерминированным МП-автоматам M1 и M2
узнать, верно ли, что L(M1) = L(M2).
Эту теорему доказал Жеро Сенизерг (Geraud Senizergues) в 1997 году. Упрощенное доказательство приводится в [Sti].
Упражнение 15.7.2.
Эквивалентны ли два изображенных ниже МП-автомата над алфавитом ?
Упражнение 15.7.3.
Эквивалентны ли два изображенных ниже МП-автомата над алфавитом ?
