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




Содержание главы


Алгоритмически разрешимые проблемы
Неукорачивающие грамматики
Линейно ограниченные автоматы
Проблема выводимости слова
Проблема пустоты языка
Проблема бесконечности языка
Проблема эквивалентности конечных автоматов
Проблема эквивалентности детерминированных МП-автоматов
Классы P и NP
Проблема неравенства регулярных выражений без итерации
Проблема неравенства регулярных выражений без итерации - часть 2



Содержание