След.: Введение Выше: Теория вычислений — Новосибирск.: Пред.: Аннотация Содержание
В первой главе вводятся основные термины, связанные с формальными языками как множествами цепочек, а также обсуждается один из самых распространенных способов задания языков - с помощью грамматик Хомского.
Во второй главе описывается ряд методов задания языков, каждый из которых в точности определяет регулярные множества — класс языков, занимающих центральное положение по отношению к значительной части теории формальных языков. Среди них — регулярные выражения, праволинейные грамматики, детерминированные и недетерминированные конечные автоматы.
В третьей главе рассматривается класс контекстно-свободных языков, который наиболее важен с точки зрения приложений к языкам программирования и трансляции, и связанный с ним класс магазинных автоматов, а также обсуждаются преобразования, которым можно подвергнуть контекстно-свободные грамматики, чтобы привести их к более удобному виду.
В четвертой главе формализуется и исследуется ряд интуитивных понятий, возникающих при решении задач дискретной математики, таких как, например, “задача”, “алгоритм”, “сложность”, “разрешимость”, “частичная разрешимость”. Изучаются неразрешимые проблемы для КС-грамматик. Вводятся недетерминированные и детерминированные машины Тьюринга и исследуются во-просы моделирования одних машин другими. Излагаются основы теории NP-полных задач и доказывается фундаментальная теорема Кука — Левина. Рассматриваются вопросы существования среди алгоритмически разрешимых проблем сколь угодно сложных задач и иерархии задач по сложности их решения, а также поиска наилучших алгоритмов решения задач.
Пятая глава посвящена сетям Петри — одной из наиболее популярных моделей параллельных систем, используемых как для теоретических исследований, так и для их практических применений в различных областях. Они используются для моделирования распре-деленных баз данных и операционных систем, архитектур вычисли-тельных машин, систем и сетей, систем программного обеспечения, протоколов коммуникаций, семантики параллельных языков, систем с элементами искусственного интеллекта и т. д. Модели сетей Петри играют такую же важную роль в изучении параллельных систем, как и конечные автоматы для последовательных систем. К достоинствам сетей Петри относятся их наглядное графическое представление и возможность автоматического анализа их свойств. В данном пособии мы рассматриваем лишь базовые понятия сетей Петри, оставляя за скобками различные приложения сетей к конкретным задачам анализа и синтеза дискретных систем.
Каждая глава снабжена упражнениями, большинство которых носят чисто тренировочный характер, но некоторые из них содержат материал, являющийся дополнением к основному тексту. Диапазон трудности упражнений весьма широк: от простых переформулировок определений до открытых проблем, завершающих каждую главу.
При изложении материала глав без определений используется ряд общеупотребительных теоретико-графовых терминов, таких как граф или дерево (см., например, [4, 5, 8]).
В главах используется двойная нумерация: например, теорема 2.3 - это третья теорема в главе 2, а лемма 5.2 - это вторая лемма в главе 5. Конец доказательства, примера или определения указывается символом “
”.
Читатель, желающий расширить свои знания по теории автоматов, формальных языков, сложности вычислений и сетям Петри, может обратиться к книгам, приведенным в библиографическом списке в конце пособия.
Учебное пособие подготовлено при частичной поддержке Российского фонда фундаментальных исследований (грант РФФИ № 18-07-00024).