Проблема эквивалентности детерминированных МП-автоматов

Теорема 15.7.1.

Существует алгоритм, позволяющий по произвольным двум детерминированным МП-автоматам M1 и M2

узнать, верно ли, что L(M1) = L(M2).

Эту теорему доказал Жеро Сенизерг (Geraud Senizergues) в 1997 году. Упрощенное доказательство приводится в [Sti].

Упражнение 15.7.2.

Эквивалентны ли два изображенных ниже МП-автомата над алфавитом ?

Упражнение 15.7.3.

Эквивалентны ли два изображенных ниже МП-автомата над алфавитом ?