Рецензии на книгу
"Введение в теорию автоматов, языков и вычислений, 2-е издание"

07.10.2004
PC Week (портал)
Сергей Бобровский
http://pcweek.ru/?ID=303253

Первое издание этой книги вышло в 1969 г., второе — спустя десять лет. Активно развивавшаяся в то время теория автоматов и языков была узкой и специфичной областью математики.

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

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

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

Их возможное применение демонстрируется на примере построения протокола, поддерживающего операции с электронными деньгами, показывается, как автоматы могут проверять протоколы обмена и находить в них изъяны. Регулярным выражениям, их свойствам и применению при построении языков программирования (в частности, командного языка Unix) посвящены третья и четвертая главы.

Класс контекстно-свободных языков (более широкий, чем класс регулярных языков) получил популярность еще в 1960-х годах, когда с его помощью создатели компиляторов стали описывать синтаксис первых языков программирования.

А сегодня он широко используется, например, при подготовке определений типов документов DTD в XML. Этому, а также их свойствам и способам задания контекстно-свободных языков автоматами с магазинной памятью отведены пятая — седьмая главы.

Большой раздел книги посвящен машине Тьюринга. Классическая формальная модель компьютера применяется для доказательств возможности компьютера решать различные задачи.

В восьмой и девятой главах рассказывается о задачах, которые невозможно решить с помощью машины Тьюринга (и соответственно с помощью любого компьютера).

Читателю наверняка будет интересно узнать о множестве весьма просто формулируемых задач, перед которыми машины бессильны. Эти главы сопровождены примерами на языке Си.

А вот поиск ответа на разрешимые проблемы требует времени, зависящего от размерности входных данных задачи либо полиномиально, либо экспотенциально (в последнем случае такие проблемы называются трудноразрешимыми).

Умение разделять проблемы по времени, необходимому для их решения, является фундаментальным при создании программ и очень актуально. Ведь не имеет смысла долго создавать сложную систему, если она не сможет находить ответ за разумное время. Со способами такого разделения можно познакомиться в двух последних главах.

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

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

20.11.2003
Открытые системы
Сергей Кузнецов

Вышедшая вторым изданием книга посвящена теории важнейшей системной модели — автоматам, которые обычно представляются как системы, состоящие из множества состояний, функций перехода и входных последовательностей. Интерес к таким моделям обнаружился в связи с огромным количеством их применений в информационных технологиях. Так, класс конечных автоматов находит широкое использование при программной и технической реализации всевозможных протоколов, при работе с различными языковыми конструкциями, в обиходе даже автоматное программирование. Данная книга включает наряду с понятийным и методологическими материалами по автоматам, в том числе и конечным. В ней рассматривается ряд структурных вопросов, среди которых проблемы доказательства эквивалентности и сложности автоматов. Уделено значительное внимание связям автоматов и регулярных языков, а также контекстно-свободных грамматик и языков, рассмотрены их свойства. Наряду с классами автоматов описаны и проблемы, которые не могут быть разрешены с их помощью: построение универсальных языков, неоднозначность контекстно-свободных грамматик. Кроме того, в книге рассмотрены вопросы сложности ряда проблем, относящихся к вычислениям с помощью автоматов. Эти главы следует рекомендовать для изучения продвинутым читателям.