Математическая теория формальных языков
Алгоритмически разрешимые проблемы
В этой лекции рассматриваются наиболее известные разрешимые проблемы, связанные с грамматиками, автоматами и регулярными выражениями. Поскольку все приведенные выше доказательства эквивалентности разных способов конечного задания формального языка были конструктивными, не важно, какой из эквивалентных способов задания языка (например, посредством контекстно-свободной грамматики или автомата с магазинной памятью) используется в точной формулировке массовой задачи.
Первые два раздела этой лекции посвящены контекстным языкам. В разделах 15.3-15.6 сформулированы теоремы о разрешимости для некоторых алгоритмических проблем. Доказательства этих теорем опираются на конструктивность рассуждений, проведенных в лекциях 3 и 8. В разделе 15.7* приводится новый неожиданный результат, доказанный в 1997 году.
Проблема эквивалентности конечных автоматов (или, что то же самое, регулярных выражений) разрешима, но, к сожалению, она сложна, то есть нахождение ответа индивидуальной задачи требует (в некотором смысле) много времени. В разделе 15.9* указывается, что даже для регулярных выражений без итерации (которые, очевидно, соответствуют конечным автоматам без циклов) проблема неэквивалентности NP-полна (необходимые определения из теории сложности вычислений приведены в разделе 15.8*).
