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

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

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

Обложка книги «Золушка» (издание 1979 года)
Автор	Джон Хопкрофт и Джеффри Ульман
Язык	Английский
Предмет	Информатика
Издатель	Эддисон-Уэсли
Дата публикации	1979
Место публикации	США
Тип носителя	Печать
ISBN	0-201-02988-X
OCLC	4549363
Десятичная система Дьюи	629.8/312
Класс LC	QA267 .H56

Введение в теорию автоматов, языки и вычисления — влиятельныйучебник по информатике Джона Хопкрофта и Джеффри Ульмана по формальным языкам и теории вычислений . Раджив Мотвани принимал участие в последующих изданиях, начиная с 2000 года.

В Jargon File прозвище книги, «Книга Золушки» , записано следующим образом: «Так названо, потому что на обложке изображена девочка (предположительно Золушка), сидящая перед устройством Руба Голдберга и держащая веревку, выходящую из него. На задней обложке устройство находится в беспорядке после того, как она (неизбежно) потянула за веревку». ^[1]

Предшественник этой книги появился под названием « Формальные языки и их связь с автоматами» в 1968 году. Эта книга, послужившая основой как для создания курсов по этой теме, так и для дальнейших исследований, сформировала область теории автоматов на протяжении более чем десятилетия, см. (Hopcroft 1989).

• Хопкрофт, Джон Э.; Ульман, Джеффри Д. (1968). Формальные языки и их связь с автоматами . Эддисон-Уэсли. ISBN 9780201029833.
• Хопкрофт, Джон Э.; Ульман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Эддисон-Уэсли. ISBN 0-201-02988-X.
• Хопкрофт, Джон Э.; Мотвани, Раджив; Ульман, Джеффри Д. (2000). Введение в теорию автоматов, языки и вычисления (2-е изд.). Эддисон-Уэсли. ISBN 81-7808-347-7.
• Хопкрофт, Джон Э.; Мотвани, Раджив; Ульман, Джеффри Д. (2006). Введение в теорию автоматов, языки и вычисления (3-е изд.). Эддисон-Уэсли. ISBN 0-321-45536-3.
• Хопкрофт, Джон Э.; Мотвани, Раджив; Ульман, Джеффри Д. (2013). Введение в теорию автоматов, языки и вычисления (3-е изд.). Pearson. ISBN 978-1292039053.

Первое издание « Введения в теорию автоматов, языки и вычисления» было опубликовано в 1979 году, второе издание — в ноябре 2000 года, а третье издание — в феврале 2006 года. После второго издания к Хопкрофту и Ульману в качестве третьего автора присоединился Раджив Мотвани . Начиная со второго издания, книга содержит расширенный обзор примеров, в которых применяется теория автоматов , тогда как большие части более продвинутой теории были удалены. Хотя это делает второе и третье издания более доступными для новичков, это делает их менее подходящими для более продвинутых курсов. Новый уклон от теории не всеми воспринимается положительно: как Шаллит цитирует одного профессора, «они удалили все хорошие части» (Шаллит 2008).

Первое издание, в свою очередь, представляло собой существенную переработку предыдущего учебника, также написанного Хопкрофтом и Ульманом, под названием « Формальные языки и их связь с автоматами» . Он был опубликован в 1968 году и упоминается во введении к изданию 1979 года. В личной исторической заметке относительно книги 1968 года Хопкрофт утверждает: «Возможно, успех книги был обусловлен нашими усилиями представить суть каждого доказательства до того, как оно будет фактически приведено» (Хопкрофт 1989). По сравнению с предыдущей книгой издание 1979 года было расширено, а материал был переработан, чтобы сделать его более доступным для студентов, ср. (Хопкрофт 1989). Это стремление к понятности ценой краткости не было воспринято положительно всеми. Как сообщает Хопкрофт в отзывах на переработанное издание 1979 года: «Похоже, наши попытки снизить уровень презентации ради студентов путем включения большего количества деталей и пояснений оказали отрицательное воздействие на преподавателей, которым затем приходилось просеивать добавленный материал, чтобы составить план и подготовить свои лекции» (Хопкрофт, 1989).

Тем не менее, наиболее цитируемым изданием книги, по-видимому, является издание 1979 года: по данным сайта CiteSeerX , более 3000 научных работ, свободно доступных в Интернете, ссылаются на это издание книги. ^[2]

• Введение в теорию вычислений Майкла Сипсера , еще один стандартный учебник в этой области
• Решения для выбранных упражнений, Стэнфордский университет

• Запись «Книга о Золушке». В: Файл Жаргона (версия 4.4.7, 29 декабря 2003 г.).
• Хопкрофт, Джон Э. (1989). «Возникновение компьютерной науки — классический комментарий к «Формальным языкам и их связи с автоматами». Текущее содержание Инженерное дело, технологии и прикладные науки . 31 : 12.доступно онлайн (pdf)
• Шаллит, Джеффри О. (2008). Второй курс по формальным языкам и теории автоматов . Cambridge University Press. стр. ix. ISBN 978-0-521-86572-2.
• "Введение в теорию автоматов, языки и вычисления - Домашняя страница". Стэнфордский университет . Архивировано из оригинала 7 июня 2023 г.