• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Глава

Полиномиальный алгоритм проверки эквивалентности детерминированных двухленточных автоматов

С. 128-130.

Показано, каким образом задача проверки эквивалентности двухленточных детерминированных автоматов может быть сведена к задаче проверки эквивалентности слабо недетерминированных конечных автоматов-преобразователей, работающих над полугруппой префиксных регулярных языков с операцией конкатенации.