Проблема эквивалентности
В теоретической информатике и теории формального языка — проблема эквивалентности это вопрос определения, учитывая два представления формальных языков, обозначают ли они один и тот же формальный язык.
Сложность и разрешимость этой проблемы решения зависят от типа рассматриваемого представления.
Например, в случае конечных автоматов эквивалентность разрешима, и проблема является PSPACE-полной .Кроме того, в случае детерминированных автоматов с выталкиванием эквивалентность разрешима, Жеро Сенизерг получил премию Гёделя за этот результат . Впоследствии было показано, что проблема кроется в TOWER, наименьшем неэлементарном классе сложности . [1]
Это становится неразрешимой проблемой для автоматических автоматов или любой машины, которая может решать контекстно-свободные или более мощные языки. [2]
Ссылки
[ редактировать ]- ^ П. Янчар. Эквиваленты систем с опусканием сложны, 2014.
- ^ Дж. Э. Хопкрофт и Дж. Д. Ульман. Введение в теорию автоматов, языки и вычисления , первое издание, 1979 г.
 | Эта по информатике статья незавершена . Вы можете помочь Википедии, расширив ее . |