Математическая теория формальных языков


         

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


Теорема 15.7.1.

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

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

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

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

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

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

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



Содержание  Назад  Вперед





Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий