Читать онлайн «Введение в теорию автоматов, языков и вычислений»

Введение в теорию автоматов, языков и вычислений 2Е ИЗДАНИЕ title. indd 1 07. 11. 2007 16:57:18  Introduction to Automata Theory, Languages, and Computation SECOND EDITION JOHN E. HOPCROFT Cornell University RAJEEV MOTWANI Stanford University JEFFREY D. ULLMAN Stanford University ADDISONWESLEY PUBLISHING COMPANY Boston · San Francisco · New York London · Toronto · Sydney · Tokyo · Singapore · Madrid Mexico City · Munich · Paris · Cape Town · Hong Kong · Montreal title. indd 2 07. 11. 2007 16:57:19  Введение в теорию автоматов, языков и вычислений 2Е ИЗДАНИЕ ДЖОН ХОПКРОФТ РАДЖИВ МОТВАНИ ДЖЕФФРИ УЛЬМАН Москва · Санкт Петербург · Киев 2008 title. indd 3 07. 11. 2007 16:57:19  ББК 32. 973. 26-018. 2. 75 Х78 УДК 681. 3. 07 Издательский дом “Вильямс” Перевод с английского О. И. Васылык, М. Саит-Аметова, канд. физ. -мат. наук А. Б. Ставровского Под редакцией канд. физ. -мат. наук А. Б. Х78 Введение в теорию автоматов, языков и вычислений, 2-е изд. . : Пер. с англ. — М. : Издательский дом “Вильямс”, 2008. — 528 с. : ил. — Парал. тит. англ. ISBN 978-5-8459-1347-0 (рус. ) Книга известных американских ученых посвящена теории автоматов и соответст- вующих формальных языков и грамматик - как регулярных, так и контекстно- свободных. Во второй части рассматриваются различные машины Тьюринга, при помо- щи которых формализуются понятия разрешимых и неразрешимых проблем, а также определяются функции временной и емкостной оценки сложности алгоритмов. Изложе- ние ведется строго, но доступно, и сопровождается многочисленными примерами, а также задачами для самостоятельного решения. Книга будет полезна читателям различных категорий - студентам, аспирантам, науч- ным сотрудникам, преподавателям высших учебных заведений, а также всем, кто инте- ресуется математическими основами современной вычислительной техники.