Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений, страница 3

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

И, наконец, последнее объяснение одновременного увеличения объема книги и уменьшения ее фактического содержания состоит в том, что при ее верстке использовались все преимугцества издательских систем ТВХ и ВТВХ, которые поощряют "открытый" стиль печати, благодаря чему книга увеличивается в объеме, но становится удобнее лля чтения. Мы с благодарностью отмечаем труд создателей этих издательских систем Дона Кнута и Леса Лампорта.

Как пользоватькя книгой Эта книга рассчитана на полусеместровый нли семестровый курс лекций для студентов второго года обучения и выше. На ее основе в Стэндфордском университете Радживом и Джеффом читается полусеместровый курс (СБ154) по теории автоматов и языков. Ввиду ограниченности по времени в этом курсе не охвачены глава 11 и часть материала главы! О, например, довольно сложные вопросы о полиномиально-временной сводимости. На ФеЬ-сайте книги (см. ниже) помещено несколько сокращенных вариантов этого курса с замечаниями. Несколько лет назад мы столкнулись с тем, что многие студенты, поступившие в Стэнфорд после окончания колледжа, прошли курс теории автоматов, не содержавший теорию сложности.

Преподавательский состав Станфорда полагает, что для всякого, кто серьезно занимается информатикой, эти идеи чрезвычайно важны. Тут недостаточно знать лишь то, что "для решения ЫР-полной задачи требуется очень много времени". Специально для таких студентов был разработан курс лекций (СЕ154Ы), который содержит материал только 8, 9 и 1О глав. Фактически, для того, чтобы освоить курс С3154Н, они прослушивают лишь последнюю треть курса СИ!54. И по сегодняшний день на каждом курсе находи~ся несколько студентов, желающих заниматься именно таким образом. Мы рекомендуем этот подход, поскольку он не требует чрезмерных усилий, Требования к уровню подготовки Чтение этой книги не вызовет затруднений у студентов, освоивших основы дискретной математики, в том числе изучивших графы, деревья, логику н методы доказательств.

Кроме того, мы предполагаем, что читатель в достаточной степени знаком с программированием и, в час~ности, имеет представление об общих структурах данных, рекурсии н роли таких главных системных компонентов, как компиляторы. Эта сумма знаний соответствует стандартной программе первых двух лет обучения для студентов, изучающих информатику. ПРЕДИСЛОВИЕ Чнражнения Книга содержит большое число упражнений, по несколько почти в каждом разделе. Упражнения или части упражнений повышенной сложности отмечены восклицательным знаком.

Наиболее трудные из них отмечены двумя восклицательными знаками. Некоторые упражнения отмечены звездочкой. Их решения мы намерены поместить на !ЧеЬ-странице книги. Они предназначены для самопроверки и доступны широкой аудитории. Отметим, что в некоторых случаях в одном упражнении Б требуется определенным образом изменить или адаптировать ваше решение другого упражнения А. Если какая-то часть упражнения А имеет решение, то естественно ожидать, что соответствующая часть упражнения Б также имеет решение.

Поддержка в ЪЧог!д ЧЧЫе ЪЧеЬ Адрес книги в 1пгегпег: Ьсср://ьляьг-с!Ь.всапйокс!.ебц/-и11шап/1а1с.Ьст1 Здесь вы найдете решения заданий, отмеченных звездочкой, список замеченных опечаток и некоторые вспомогательные материалы. По мере чтения лекций по курсу СБ! 54 мы постараемся размещать тут наши замечания по поводу домашних заданий, решений упражнений и экзаменов. Благодарности На часть материала главы ! повлияла рукопись Крейга Сильверштейна (Сге!я Б!!чегме)п) о том, "как строить доказательства".

Мы благодарим также следующих лиц: Зое Абрамс (Еое АЬгашз), Джордж Кандеа (Оеогяе Сапдеа), Хаовен Чен (Наошеп СЬеп), Бьеи-Ган Чан (Вуопя-Опп СЬпп), Джеффри Шаллит ()е(тгеу БЬа111!), Брет Тейлор (Вге! Тау1ог), Джейсон Таунсенд ()акоп Товпзепг() и Эрик Узурео (Егйк ()когеаи), которые высказали свои замечания и указали на ряд опечаток в черновом варианте книги. Ошибки, оставшиеся незамеченными, авторы безусловно относят на свой счет. Джон Хопкрофт Раджив Мотвани Джефри Ульман Итака, Нью-Иорк и Стэнфорд, Калифорния Сентябрь, 2000.

16 ПРЕДИСЛОВИЕ ГЛАВА 1 Автоматы: методы и понятия Теория автоматов занимается изучением абстрактных вычислительных устройств, или "машин". В 1930-е годы, задолго до появления компьютеров, А. Тьюринг исследовал абстрактную машину, которая, по крайней мере в области вычислений, обладала всеми возможностями современных вычислительных машин. Целью Тьюринга было точно описать границу между тем, что вычислительная машина может делать, и тем, чего она не может.

Полученные им результаты применимы не только к абстрактным машинам Тьюранга, но и к реальным современным компьютерам. В 1940-х и 1950-х годах немало исследователей занимались изучением простейших машин, которые сегодня называются "конечными автоматами". Такие автоматы вначале были предложены в качестве модели функционирования человеческого мозга.

Однако вскоре они оказались весьма полезными для множества других целей, которые будут упомянуты в разделе 1.1. А в конце 1950-х лингвист Н. Хомский занялся изучением формальных "грамматик". Не будучи машинами в точном смысле слова, грамматики, тем не менее, тесно связаны с абстрактными автоматами и служат основой некоторых важнейших составляющих программного обеспечения, в частности, компонентов компиляторов.

В 19б9 году С. Кук развил результаты Тьюринга о вычислимости и невычислимости. Ему удалось разделить задачи на те, которые могут быть эффективно решены вычислительной машиной, и те, которые, в принципе, могут быть решены, но требуют для этого так много машинного времени, что компьютер оказывается бесполезным для решения практически всех экземпляров задачи, за исключением небольших. Задачи последнего класса называют "трудно разрешимыми*' ("труднорешаемыми") или "1ЧР-трудными". Даже при экспоненциальном росте быстродействия вычислительных машин (" закон Муф') весьма маяовероятно, что нам удастся достигнуть значительных успехов в решении задач этого класса.

Все эти теоретические построения непосредственно связаны с тем, чем занимаются ученые в области информатики сегодня. Некоторые из введенных понятий, такие, например, как конечные автоматы и некоторые типы формальных грамматик, используются при проектировании и создании важных компонентов программного обеспечения. Другие понятия, например, машина Тьюринга, помогают нам уяснить принципиальные возможности программного обеспечения. В частности, теория сложности вычислений позволяет определить, можем ли мы решить ту или иную задачу "в лоб" и написать соответствуюшую программу для ее решения (если эта задача не принадлежит классу "трудно разрешимых"), или же нам следует искать решение данной трудно разрешимой задачи в обход, используя приближенный, эвристический, или какой-либо другой метод, с помошью которого удастся ограничить время, затрачиваемое программой на ее решение. В этой вводной главе дается обзор содержания теории автоматов и ее приложений.

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

В этом разделе мы познакомим читателя с главными мотивами, побуждающими нас к их изучению, а также обрисуем в обших чертах основные темы, затрагиваемые в книге. 1.1.1. Введение в теорию конечных автоматов Конечные автоматы являются моделью для многих компонентов аппаратного и программного обеспечения. Ниже (начиная со второй главы) мы рассмотрим примеры их использования, а сейчас просто перечислим наиболее важные из них. К Программное обеспечение, используемое для разработки и проверки цифровых схем. 2.