Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. Пер. с англ. М.: Издательский дом “Вильямс”, 2002. - 528 с.
Первое издание этой книги вышло в 1969 г., второе - спустя десять лет. Активно развивавшаяся в то время теория автоматов и языков была узкой и специфичной областью математики. Но сегодня она почти сформировалась, хотя появилось множество ее прикладных приложений, связанных с ИТ. Оказалось, что рассматриваемые в этой теории подходы к построению алгоритмов весьма точно отвечают потребностям современной программной инженерии, заинтересованной в автоматизации процессов создания качественного ПО. Поэтому третье издание во многом сосредоточилось на практических аспектах изучаемой области.
Основным понятиям теории автоматов посвящена первая глава книги. Ее приложения востребованы прежде всего в задачах разработки цифровых схем, создания компиляторов, поисковых систем и программ проверки протоколов. Во второй главе рассматриваются языки, которые могут быть описаны конечными автоматами. Их возможное применение демонстрируется на примере построения протокола, поддерживающего операции с электронными деньгами, показывается, как автоматы могут проверять протоколы обмена и находить в них изъяны. Регулярным выражениям, их свойствам и применению при построении языков программирования (в частности, командного языка Unix) посвящены третья и четвертая главы.
Класс контекстно-свободных языков (более широкий, чем класс регулярных языков) получил популярность еще в 1960-х годах, когда с его помощью создатели компиляторов стали описывать синтаксис первых языков программирования. А сегодня он широко используется, например, при подготовке определений типов документов DTD в XML. Этому, а также их свойствам и способам задания контекстно-свободных языков автоматами с магазинной памятью отведены пятая - седьмая главы.
Большой раздел книги посвящен машине Тьюринга. Классическая формальная модель компьютера применяется для доказательств возможности компьютера решать различные задачи. В восьмой и девятой главах рассказывается о задачах, которые невозможно решить с помощью машины Тьюринга (и соответственно с помощью любого компьютера). Читателю наверняка будет интересно узнать о множестве весьма просто формулируемых задач, перед которыми машины бессильны. Эти главы сопровождены примерами на языке Си.
А вот поиск ответа на разрешимые проблемы требует времени, зависящего от размерности входных данных задачи либо полиномиально, либо экспотенциально (в последнем случае такие проблемы называются трудноразрешимыми). Умение разделять проблемы по времени, необходимому для их решения, является фундаментальным при создании программ и очень актуально. Ведь не имеет смысла долго создавать сложную систему, если она не сможет находить ответ за разумное время. Со способами такого разделения можно познакомиться в двух последних главах.
Каждую главу сопровождают различные задачи. Советую программистам потрудиться над их разбором. Процесс решения и построение формальных алгоритмов часто встречающихся задач можно значительно улучшить за счет эффективности подготовки программного кода.
Книга будет полезна разработчикам, стремящимся повысить личное мастерство, студентам соответствующих специальностей и всем интересующимся современным состоянием теории автоматов и ее практическими приложениями.
