Предисловие
В предисловии к своей книге 1979 года, предшествовавшей данному изданию, Дж. Хопкрофт и Дж. Ульман с удивлением отмечали, что за время, прошедшее после выхода их первой книги в 1969 году, произошел взрыв в развитии теории автоматов. Действительно, книга, вышедшая в 1979 году, содержала множество тем, не затронутых в предыдущей работе, и по объему была почти вдвое больше. Сравнив эту книгу с книгой 1979 года, вы увидите, что она, как автомобили 1970-х «больше снаружи, но меньше изнутри». И хотя это может показаться шагом назад, мы считаем такие изменения целесообразными в силу ряда причин.

Во-первых, в 1979 году теория автоматов и языков еще активно развивалась, и одной из целей той книги было пробудить интерес математически одаренных студентов к исследованиям в этой области. На сегодня в теории автоматов имеется лишь узкое направление для исследований (чего не скажешь о ее приложениях). Поэтому, на наш взгляд, не имеет смысла сохранять здесь лаконичный, сугубо математический стиль книги 1979 года.
Во-вторых, за последние двадцать лет изменилась роль теории автоматов и языков. В 1979 году это был сложный предмет, требующий от читателя высокого уровня подготовки. Читатель нашей книги, в особенности последних ее глав, представлялся нам хорошо подготовленным студентом-старшекурсником. Сегодня же этот предмет входит в стандартную вузовскую программу для младших курсов. Поэтому содержание книги должно быть по возможности доступным, а следовательно, содержать больше подробных доказательств и обоснований по сравнению с предыдущей книгой.
В-третьих, за два последних десятилетия информатика (Computer Science) невообразимо разрослась. И если в 1979 году вузовскую программу приходилось искусственно заполнять предметами, которые, как нам казалось, могли послужить новой волне развития технологий, то сегодня таких дисциплин уже слишком много.
В-четвертых, за эти годы информатика стала практическим предметом, и многие изучающие ее студенты настроены прагматически. Мы по-прежнему убеждены, что теория автоматов является мощным инструментом для исследований во множестве новых областей. А упражнения теоретического, развивающего плана, которые содержит обычный курс теории автоматов, сохраняют свое значение вне зависимости от того, предпочитает ли студент изучать лишь практические, «денежные» технологии. Однако для того, чтобы обеспечить данному предмету достойное место среди прочих дисциплин, изучаемых студентами-информатиками, нам представляется необходимым, наряду с математической частью, подчеркнуть и практические приложения теории. С этой целью мы заменили часть довольно сложных для понимания тем из предыдущей книги актуальными примерами применения этих идей на практике. В то время как приложения теории автоматов и языков для компиляторов сегодня настолько понятны и естественны, что входят во всякий стандартный курс по компиляторам, существует немало и совершенно новых приложений. Например, алгоритмы проверки моделей, используемые для верификации протоколов, и языки описания документов, построенные по образцу контекстно- свободных грамматик.
И, наконец, последнее объяснение одновременного увеличения объема книги и уменьшения ее фактического содержания состоит в том, что при ее верстке использовались все преимущества издательских систем TgX и I^TgX, которые поощряют «открытый» стиль печати, благодаря чему книга увеличивается в объеме, но становится удобнее для чтения. Мы с благодарностью отмечаем труд создателей этих издательских систем Дона Кнута и Леса Лампорта.
Как пользоваться книгой
Эта книга рассчитана на полусеместровый или семестровый курс лекций для студентов второго года обучения и выше. На ее основе в Стэндфордском университете Раджи- вом и Джеффом читается полу семестровый курс (CS154) по теории автоматов и языков. Ввиду ограниченности по времени в этом курсе не охвачены глава 11 и часть материала главы 10, например, довольно сложные вопросы о полиномиально-временной сводимости. На Web-сайте книги (см. ниже) помещено несколько сокращенных вариантов этого курса с замечаниями.
Несколько лет назад мы столкнулись с тем, что многие студенты, поступившие в Стэнфорд после окончания колледжа, прошли курс теории автоматов, не содержавший теорию сложности. Преподавательский состав Стэнфорда полагает, что для всякого, кто серьезно занимается информатикой, эти идеи чрезвычайно важны. Тут недостаточно знать лишь то, что «для решения NP-полной задачи требуется очень много времени». Специально для таких студентов был разработан курс лекций (CS154N), который содержит материал только 8, 9 и 10 глав. Фактически, для того, чтобы освоить курс CS154N, они прослушивают лишь последнюю треть курса CS154. И по сегодняшний день на каждом курсе находится несколько студентов, желающих заниматься именно таким образом. Мы рекомендуем этот подход, поскольку он не требует чрезмерных усилий.
Требования к уровню подготовки
Чтение этой книги не вызовет затруднений у студентов, освоивших основы дискретной математики, в том числе изучивших графы, деревья, логику и методы доказательств. Кроме того, мы предполагаем, что читатель в достаточной степени знаком с программированием и, в частности, имеет представление об общих структурах данных, рекурсии и роли таких главных системных компонентов, как компиляторы. Эта сумма знаний соответствует стандартной программе первых двух лет обучения для студентов, изучающих информатику.
Упражнения
Книга содержит большое число упражнений, по несколько почти в каждом разделе. Упражнения или части упражнений повышенной сложности отмечены восклицательным знаком. Наиболее трудные из них отмечены двумя восклицательными знаками.
Некоторые упражнения отмечены звездочкой. Их решения мы намерены поместить на Web-странице книги. Они предназначены для самопроверки и доступны широкой аудитории. Отметим, что в некоторых случаях в одном упражнении Б требуется определенным образом изменить или адаптировать ваше решение другого упражнения А. Если какая-то часть упражнения А имеет решение, то естественно ожидать, что соответствующая часть упражнения Б также имеет решение.
Поодержка в World Wide Web
Адрес книги в Internet: www-db.Stanford.edu/~ullman/ialc.html
Здесь вы найдете решения заданий, отмеченных звездочкой, список замеченных опечаток и некоторые вспомогательные материалы. По мере чтения лекций по курсу CS154 мы постараемся размещать тут наши замечания по поводу домашних заданий, решений упражнений и экзаменов.
Благодарности
На часть материала главы 1 повлияла рукопись Крейга Сильверштейна (Creig Silver- stein) о том, «как строить доказательства». Мы благодарим также следующих лиц: Зое Абраме (Zoe Abrams), Джордж Кандеа (George Candea), Хаовен Чен (Haowen Chen), Бьен-Ган Чан (Byong-Gun Chun), Джеффри Шаллит (Jeffrey Shallit), Брет Тейлор (Bret Taylor), Джейсон Таунсенд (Jason Townsend) и Эрик Узурео (Erik Uzureau), которые высказали свои замечания и указали на ряд опечаток в черновом варианте книги. Ошибки, оставшиеся незамеченными, авторы безусловно относят на свой счет.
Джон Хопкрофт Раджив Мотвани Джефри Ульман
Итака, Нью-Йорк и Стэнфорд, Калифорния Сентябрь, 2000.

ГЛАВА 1
Автоматы: методы и понятия
Теория автоматов занимается изучением абстрактных вычислительных устройств, или «машин». В 1930-е годы, задолго до появления компьютеров, А. Тьюринг исследовал абстрактную машину, которая, по крайней мере в области вычислений, обладала всеми возможностями современных вычислительных машин. Целью Тьюринга было точно описать границу между тем, что вычислительная машина может делать, и тем, чего она не может. Полученные им результаты применимы не только к абстрактным машинам Тьюринга, но и к реальным современным компьютерам.
В 1940-х и 1950-х годах немало исследователей занимались изучением простейших машин, которые сегодня называются «конечными автоматами». Такие автоматы вначале были предложены в качестве модели функционирования человеческого мозга. Однако вскоре они оказались весьма полезными для множества других целей, которые будут упомянуты в разделе 1.1. А в конце 1950-х лингвист Н. Хомский занялся изучением формальных «грамматик». Не будучи машинами в точном смысле слова, грамматики, тем не менее, тесно связаны с абстрактными автоматами и служат основой некоторых важнейших составляющих программного обеспечения, в частности, компонентов компиляторов.
В 1969 году С. Кук развил результаты Тьюринга о вычислимости и невычислимости. Ему удалось разделить задачи на те, которые могут быть эффективно решены вычислительной машиной, и те, которые, в принципе, могут быть решены, но требуют для этого так много машинного времени, что компьютер оказывается бесполезным для решения практически всех экземпляров задачи, за исключением небольших. Задачи последнего класса называют «трудно разрешимыми» («труднорешаемыми») или «NP-трудными». Даже при экспоненциальном росте быстродействия вычислительных машин («закон Мура») весьма маловероятно, что нам удастся достигнуть значительных успехов в решении задач этого класса.
Все эти теоретические построения непосредственно связаны с тем, чем занимаются ученые в области информатики сегодня. Некоторые из введенных понятий, такие, например, как конечные автоматы и некоторые типы формальных грамматик, используются при проектировании и создании важных компонентов программного обеспечения. Другие понятия, например, машина Тьюринга, помогают нам уяснить принципиальные возможности программного обеспечения. В частности, теория сложности вычислений позволяет определить, можем ли мы решить ту или иную задачу «в лоб» и написать соответствующую программу для ее решения (если эта задача не принадлежит классу «трудно разрешимых»), или же нам следует искать решение данной трудно разрешимой задачи в обход, используя приближенный, эвристический, или какой-либо другой метод, с помощью которого удастся ограничить время, затрачиваемое программой на ее решение.
В этой вводной главе дается обзор содержания теории автоматов и ее приложений. Основная часть главы посвящена рассмотрению различных методов доказательств и способов их нахождения. Рассматриваются дедуктивные доказательства, утверждения, получаемые переформулировкой, доказательства от противного, доказательства по индукции и другие важные понятия. В последней части вводится ряд основополагающих понятий теории автоматов: алфавиты, цепочки и языки.
1.1. Зачем изучается теория автоматов?
В силу ряда причин теория автоматов и теория сложности являются важнейшей частью ядра информатики. В этом разделе мы познакомим читателя с главными мотивами, побуждающими нас к их изучению, а также обрисуем в общих чертах основные темы, затрагиваемые в книге.
1.1.1. Введение в теорию конечных автоматов
Конечные автоматы являются моделью для многих компонентов аппаратного и программного обеспечения. Ниже (начиная со второй главы) мы рассмотрим примеры их использования, а сейчас просто перечислим наиболее важные из них.
1. Программное обеспечение, используемое для разработки и проверки цифровых схем.
2. «Лексический анализатор» стандартного компилятора, т.е. тот компонент компилятора, который отвечает за разбивку исходного текста на такие логические единицы, как идентификаторы, ключевые слова и знаки пунктуации.
3. Программное обеспечение для сканирования таких больших текстовых массивов, как наборы Web-страниц, с целью поиска заданных слов, фраз или других последовательностей символов (шаблонов).
4. Программное обеспечение для проверки различного рода систем (протоколы связи или протоколы для защищенного обмена информацией), которые могут находиться в конечном числе различных состояний.
С точными определениями автоматов различного типа мы встретимся вскоре. А начнем с краткого описания того, что представляет собой конечный автомат, и как он действует. Существует множество различных систем и их компонентов, например, только что перечисленные, которые можно рассматривать, как находящиеся в каждый момент времени в одном из конечного числа «состояний». Назначением каждого состояния является запоминание определенного момента истории системы. Поскольку число состояний конечно, то запомнить всю историю системы невозможно, а значит, необходимо строить систему тщательно, чтобы хранить только действительно важную информацию и забывать несущественную. Преимущество конечности числа состояний заключается в том, что систему можно реализовать, имея ограниченные ресурсы. Например, ее можно реализовать «в железе» как схему или же в виде простой программы, принимающей решения на основе ограниченного количества данных или текущей команды машинного кода.
Пример 1.1. Простейшим нетривиальным конечным автоматом является переключатель «включено-выключено». Это устройство помнит свое текущее состояние, и от этого состояния зависит результат нажатия кнопки. Из состояния «выключено» нажатие кнопки переводит переключатель в состояние «включено», и наоборот.
На рис. 1.1 представлена конечноавтоматная модель переключателя. Как и для всех конечных автоматов, состояния обозначены кружками. В данном случае они отмечены как «вкл.» и «выкл.». Дуги между состояниями отмечены «входными символами», задающими внешние воздействия на систему. В нашем случае это Нажатие, что означает нажатие на кнопку переключателя. Стрелки указывают, что всякий раз при Нажатии система переходит из одного состояния в другое.
Нажатие

Рис. 1.1. Конечный автомат, моделирующий переключатель

Одно из состояний является так называемым «начальным состоянием». Это состояние (в нашем случае— «выкл»), в котором система находится изначально. На рисунке оно отмечено словом Начало и стрелкой, указывающей на это состояние.
Часто необходимо выделять одно или несколько «заключительных», или «допускающих», состояний. Попав в одно из них в результате реализации некоторой последовательности входных воздействий, мы можем считать такую входную последовательность в определенном смысле «хорошей». Так, например, состояние «вкл.» на рис. 1.1 можно рассматривать как допускающее, поскольку если переключатель находится в этом состоянии, то устройство, управляемое им, находится в рабочем режиме. Допускающие состояния принято обозначать двойным кружком, хотя мы не использовали это обозначение на рис 1.1. □
Пример 1.2. Иногда состояние автомата запоминает гораздо более сложную информацию, чем выбор «вкл.-выкл.». На рис. 1.2 представлен конечный автомат, который может служить частью лексического анализатора. Его функцией является распознавание ключевого слова then. Этот автомат должен иметь пять различных состояний, каждое из которых представляет позицию в слове then, достигнутую на данный момент. Эти позиции соответствуют префиксам слова, от пустой цепочки (никакая позиция в слове еще не достигнута) до целого слова.

Начало
Рис. 1.2. Конечный автомат, моделирующий распознавание слова then

На рис. 1.2 каждое из пяти состояний обозначено частью слова, прочитанной на данном шаге. Входным сигналам соответствуют буквы. Мы можем считать, что данный лексический анализатор всякий раз просматривает по одному символу компилируемой программы. Каждый следующий символ рассматривается как входной сигнал для данного автомата. Начальное состояние автомата соответствует пустой цепочке, и каждое состояние имеет переход по очередной букве слова then в состояние, соответствующее следующему префиксу. Состояние, обозначенное словом «then», достигается, когда по буквам введено все данное слово. Поскольку функция автомата заключается в распознавании слова then, то последнее состояние будем считать единственным допускающим.
1.1.2. Структурные представления
Следующие системы записи не являются автоматными, но играют важную роль в теории автоматов и ее приложениях.
1. Грамматики. Они являются полезными моделями при проектировании программного обеспечения, обрабатывающего данные рекурсивной структуры. Наиболее известный пример — «синтаксический анализатор». Этот компонент компилятора работает с такими рекурсивно вложенными конструкциями в типичных языках программирования, как выражения: арифметические, условные и т.п. Например, грамматическое правило типа Е =Ф Е + Е означает, что выражение может быть получено соединением любых двух выражений с помощью знака «плюс». Это типичное правило построения выражений в существующих языках программирования. Ниже, в главе 5, будут определены так называемые контекстно-свобод- ные грамматики.
2. Регулярные выражения. Они также задают структуру данных, в частности, текстовых цепочек. Как будет показано в главе 3, шаблоны описываемых ими цепочек представляют собой то же самое, что задают конечные автоматы. Стиль этих выражений существенно отличается от стиля, используемого в грамматиках. Ограничимся простым примером. Регулярное выражение в стиле UNIX ‘ [A-z] [a-z] * [ ] [A-Z] [A-Z] ‘ представляет множество слов, начинающихся с прописной буквы, за которыми следуют пробел и две прописные буквы. В тексте такое выражение задает шаблоны, которые могут быть названиями города и штата, например: Ithaca NY (Итака, штат Нью-Йорк). В этом выражении не учтено, что название города может состоять из нескольких слов, к примеру: Palo Alto СА (Пало-Альто, штат Калифорния). Чтобы учесть этот случай, приходится использовать более сложное выражение: ‘ ( [A-Z] [a-z]*[ ])*[ ] [A-Z] [A-Z] ‘. Для интерпретации подобных выражений достаточно знать лишь то, что [A-Z] означает последовательность прописных букв английского алфавита от «А» до «Z» (т.е. любую прописную букву), а [ ] означает одиночный пробел. Кроме того, * значит «любое число вхождений» предшествующего выражения. Круглые скобки используются для группировки членов выражения и не являются символами описываемого текста.
1.1.3. Автоматы и сложность
Автоматы являются существенным инструментом исследования пределов вычислимости. Как мы уже упоминали в начале главы, существуют следующие две важные проблемы.
1. Что компьютер вообще может? Это вопрос «разрешимости», а задачи, которые могут быть решены с помощью компьютера, называют «разрешимыми». Этой теме посвящена глава 9.
2. Что компьютер может делать эффективно? Это вопрос «труднорешаемости» задач. Те задачи, на решение которых компьютеру требуется время, зависящее от размера входных данных как некоторая медленно растущая функция, называют «легко разрешимыми». «Медленно растущими» функциями чаще всего считаются полиномиальные, а функции, которые растут быстрее, чем любой полином, считают растущими слишком быстро. Этот круг вопросов изучается в главе 10.
1.2. Введение в теорию формальных доказательств
Если вам довелось изучать планиметрию в школе до начала 1990-х, то, вероятнее всего, вам приходилось проводить подробные «дедуктивные доказательства» шаг за шагом, последовательно и детально обосновывая истинность некоторого утверждения. Поскольку геометрия имеет свою практическую сторону (например, если вы хотите приобрести нужное количество коврового покрытия для комнаты, то вам нужно знать правило вычисления площади прямоугольника), постольку и изучение общих методик формального доказательства в школе считалось весьма важным.
В 1990-х годах в США стало модным учить доказательствам, основанным на субъективных ощущениях относительно истинности утверждения. Конечно, неплохо уметь чувствовать истинность необходимого вам утверждения, однако плохо то, что в школе теперь не изучают весьма важные методики доказательств. А между тем, всякий, кто занимается информатикой, должен уметь понимать доказательства. Некоторые специалисты в области информатики придерживаются крайней точки зрения, полагая, что формальное доказательство корректности программы должно идти рука об руку с ее написанием. Продуктивность такого подхода вызывает сомнение. С другой стороны, есть и такие, которые считают, что в программировании как дисциплине нет места доказательствам. Среди них популярен девиз: «Если ты не уверен в правильности своей программы— запусти ее и убедись».
Мы занимаем промежуточную позицию по отношению к этим полярным подходам. Тестирование программ, безусловно, важно. Однако тестирование проходит до поры до времени, поскольку вы не в состоянии проверить работу вашей программы для всех возможных входных данных. Важнее, что, если ваша программа достаточно сложна (скажем, какая-нибудь хитрая рекурсия или итерация), то, не зная точно, что происходит при входе в цикл или рекурсивном вызове некоторой функции, вы вряд ли сумеете верно записать код. Получив сообщение об ошибке, вам все равно придется искать правильное решение.
Чтобы правильно выполнить рекурсию или итерацию, необходимо предварительно построить некую индуктивную гипотезу, причем полезно обосновать формально или неформально, что эта гипотеза остается истинной при рекурсии или итерации. В сущности, процедура уяснения механизма работы правильно написанной программы — это то же самое, что процедура доказательства по индукции теоремы. Поэтому наряду с моделями, полезными для различных видов программного обеспечения, в курсе теории автоматов традиционно изучают и методы формальных доказательств. Теория автоматов, пожалуй, в большей степени, чем все остальные предметы, лежащие в основе информатики, прибегает к естественным и содержательным доказательствам, как дедуктивным (состоящим из последовательности обоснованных шагов), так и индуктивным. Последние представляют собой рекурсивные доказательства параметризованных утверждений, в которых используется само утверждение с «меньшими» значениями параметра.
1.2.1. Дедуктивные доказательства
Как указывалось выше, дедуктивное доказательство состоит из последовательности утверждений, истинность которых следует из некоторого исходного утверждения, называемого гипотезой, или данным утверждением (данными утверждениями), или посылкой. Конечное утверждение этой цепочки называется заключением. Каждый шаг дедуктивного доказательства делается в соответствии с некоторыми допустимыми логическими принципами на основании либо известных фактов, либо предыдущих утверждений, либо комбинации тех и других.
Исходная гипотеза может быть истинной или ложной. Обычно это зависит от значений входящих в нее параметров. Часто гипотеза содержит несколько независимых утверждений, связанных логическим союзом «И». В таких случаях каждое из этих утверждений считается гипотезой или данным утверждением.
Теорема, которую мы доказываем, переходя от гипотезы Н к заключению С, является утверждением вида «если Н, то С». Мы говорим, что С логически (дедуктивно) следует из Н. Следующая теорема служит иллюстрацией утверждения данного типа.
Теорема 1.3. Если х > 4, то 2х > х2. □
Формальное доказательство теоремы 1.3, основанное на индукции, мы рассмотрим в примере 1.17. Неформальное же доказательство этой теоремы особых усилий не требует. Для начала отметим, что гипотезой Я является утверждение «х > 4». Эта гипотеза зависит от параметра х, а потому не является ни истинной, ни ложной. Истинность Н зависит от значения параметра х: так, например, при х = 6 она верна, а при х = 2 — ложна.
Точно так же заключение С — это утверждение «2х > х2». Данное утверждение также зависит от параметра х и является истинным при одних значениях параметра и ложным — при других. Например, С ложно при х = 3, поскольку 23 = 8 не превышает З2 = 9. С другой стороны, С истинно при х = 4, так как 24 = 42 = 16. Для х = 5 утверждение также истинно, поскольку 25 = 32 не меньше, чем 52 = 25.
Интуиция наверняка вам подсказывает, что утверждение 2х > х2 истинно при х > 4. В его истинности при х = 4 мы уже убедились. Если х > 4 и х возрастает, то 2х удваивается всякий раз, когда значение х увеличивается на 1. При этом выражение х2, стоящее в правой части, увеличивается в ((х + 1 )/х)2 раз. Если х>4, то ((х + 1)/jc) не превышает 1.25, следовательно, ((х + 1 )/х)2 не превышает 1.5625. Поскольку 1.5625 < 2, то при х >4 с ростом х левая часть 2х растет быстрее, чем правая х2. Таким образом, если, начиная со значения х, при котором неравенство 2х > х2 выполняется, например для х = 4, мы увеличиваем х, то неравенство остается верным.
Мы завершили неформальное, но вполне аккуратное доказательство теоремы 1.3. К более строгому доказательству этой теоремы мы еще вернемся в примере 1.17, после того как познакомимся с «индуктивными» доказательствами.
Как и все содержательные теоремы, теорема 1.3 охватывает бесконечное число связанных между собой фактов. В данном случае для всех целых х имеем «если х > 4, то 2х >х2». На самом деле, необязательно предполагать, что х— целое. Но, поскольку в доказательстве теоремы говорится лишь об х, возрастающих на единицу, начиная с х = 4, то в действительности теорема доказана только для целых х.
Из теоремы 1.3 можно вывести ряд других теорем. В следующем примере мы рассмотрим полное дедуктивное доказательство простой теоремы, использующее теорему 1.3.
Теорема 1.4. Если х является суммой квадратов четырех положительных целых чисел, то 2Л > х.
Доказательство. На интуитивном уровне идея доказательства состоит в том, что если предположение данной теоремы верно для некоторого х, то, поскольку х — сумма квадратов четырех положительных целых чисел, значение х по крайней мере не меньше 4. Но тогда выполнено условие теоремы 1.3, а поскольку мы считаем, что она верна, то мы можем утверждать, что и заключение этой теоремы справедливо для х. Рассуждения можно представить в виде последовательности шагов, каждый из которых является либо гипотезой доказываемой теоремы, либо ее частью, либо утверждением, которое следует из одного или нескольких предыдущих утверждений.
Под словом «следует» мы подразумеваем, что, если предыдущим утверждением является гипотеза какой-либо теоремы, то заключение этой теоремы верно и может быть записано, как утверждение в нашем доказательстве. Это логическое правило часто называют правилом modus ponens. Оно гласит, что, если известно, что утверждение Я истинно и утверждение «если Я, то С» истинно, то можно заключить, что С также истинно. Кроме того, при выводе утверждений из одного или нескольких предыдущих утверждений допустимы и другие логические шаги. Так, например, если А и В — два предыдущих утверждения, то мы можем вывести и записать утверждение «А и В».
На рис. 1.3 приведена вся последовательность утверждений, необходимых для доказательства теоремы 1.4. Отметим, что мы не собираемся доказывать теоремы в такой стилизованной форме, хотя она помогает представить доказательство в виде явного перечня строго обоснованных утверждений. На шаге (1) мы повторяем одну из посылок теоремы: х есть сумма квадратов четырех целых чисел. В доказательствах часто оказывается полезным как-то обозначать величины. Здесь четыре целых числа обозначены как а, Ь, с и d.
Утверждение Обоснование
1. х = а2 + Ь2 + с2 + d2 Посылка
2. а> 1; b> 1; с> 1; d> 1 Посылка
3. а2 > 1 ;b2> 1; с2 > 1; cf> 1 (2) и свойства арифметики
4. х > 4 (1), (3) и свойства арифметики
5. 2х > х2 (4) и теорема 1.3
Рис. 1.3. Формальное доказательство теоремы 1.4

На шаге 2 записана еще одна часть предположения теоремы: каждое из чисел, возводимых в квадрат, не меньше 1. Технически, это утверждение содержит в себе четыре отдельных утверждения для каждого из данных четырех целых чисел. Затем, на шаге 3, замечаем, что квадрат числа, не меньшего 1, также не меньше 1. В качестве обоснования используется истинность утверждения 2 и «свойства арифметики», т.е. мы предполагаем, что читатель знает или может самостоятельно вывести простые утверждения с неравенствами, такие как: «еслиу > 1, то_у2 > 1».
На шаге 4 используются утверждения 1 и 3. В первом из них говорится, что х есть сумма четырех квадратов, а во втором — что каждый из квадратов не меньше 1. Воспользовавшись известными свойствами арифметики, заключаем, что минимальное значение х равно 1 + 1 + 1 + 1, т.е. 4.
На последнем шаге 5 используем утверждение 4, которое является гипотезой теоремы 1.3. Теорема же сама по себе есть основание, благодаря которому мы можем выписать ее заключение, поскольку предыдущее утверждение является ее предположением. Так как утверждение 5, т.е. заключение теоремы 1.3, является также заключением теоремы 1.4, то теорема 1.4 доказана. Таким образом, исходя из предположения теоремы, нам удалось вывести ее заключение. □
1.2.2. Сведение к определениям
В двух предыдущих теоремах использовались такие хорошо известные понятия, как целые числа, сложение и умножение. Во многих других теоремах, в том числе во многих теоремах теории автоматов, понятия, используемые в утверждениях, могут быть не столь очевидными. Для многих доказательств оказывается полезным следующее правило.
• Если вы не знаете, с чего начать доказательство, то замените все понятия, входящие в гипотезу, их определениями.
Приведем пример теоремы, которую легко доказать, переписав ее утверждение в элементарных терминах. В ней используются следующие определения.
1. Множество S называется конечным, если существует целое число п, и S содержит ровно п элементов. Мы пишем ||5|| = п, где ||5|| обозначает число элементов во множестве S. Если множество S не является конечным, то его называют бесконечным. Интуитивно бесконечное множество можно представлять как множество, число элементов которого больше любого целого числа.
• Если множества S и Г являются подмножествами некоторого множества U, то говорят, что Т есть дополнение S (относительно множества U), если SU Т= U и
5f| Т = 0. Таким образом, всякий элемент U содержится в одном, и только в одном, из множеств S или Т. Другими словами, в Т содержатся те, и только те, элементы U, которые не содержатся в S.
Теорема 1.5. Пусть S— конечное подмножество бесконечного множества U, и пусть Т— дополнение S относительно U. Тогда Т— бесконечное множество.
Доказательство. Интуитивно утверждение теоремы гласит, что, если имеется бесконечный запас чего-либо (U), и из него изымается конечное количество (S), то оставшееся содержимое по-прежнему бесконечно. Для начала перепишем положения теоремы так, как показано на рис. 1.4.
Исходное утверждение Новое утверждение
S конечно Существует целое п и ||5|| = п
U бесконечно Не существует целого р, при котором ||СЦ =р
Т является дополнением S sy С/и5П Г= 0
Рис. 1.4. Переформулировка положений теоремы 1.5
Чтобы сдвинуться с места в нашем доказательстве, мы должны применить общий метод, называемый «доказательством от противного». Применяя этот метод, который обсуждается в разделе 1.3.3, мы предполагаем, что заключение теоремы ложно. Затем, основываясь на этом предположении и отдельных утверждениях гипотезы теоремы, доказываем утверждение, являющееся отрицанием какого-либо из утверждений гипотезы. Этим мы показываем, что невозможно, чтобы одновременно все части гипотезы были истинными, а заключение— ложным. Остается единственная возможность — сделать вывод, что заключение истинно, если истинна гипотеза, т.е. что теорема верна.
В теореме 1.5 отрицанием заключения является «Т— конечное множество». Предположим, что Т— конечно, вместе с утверждением гипотезы о конечности S, т.е. ||5|| = п при некотором целом п. Наше предположение можно переформулировать в виде «||7]| = m для некоторого целого числа т».
Одна из посылок утверждает, что S U Т = U и S Г) Т = 0, т.е. каждый элемент U принадлежит в точности одному из множеств S или Т. Но тогда в U должно содержаться п + m элементов. Поскольку п + m — целое число, и, как показано, ||£/|| = п + пг, то U — конечное множество. Точнее, мы показали, что число элементов U есть целое число, что соответствует определению конечного множества. Но утверждение, что U — конечно, противоречит условию теоремы, согласно которому U — бесконечное множество. Таким образом, предположив противное заключению теоремы, мы получили противоречие одному из данных утверждений ее гипотезы. Согласно принципу «доказательства от противного» приходим к выводу, что теорема верна. □
Доказательства не обязательно должны быть столь подробными. Зная идею доказательства, мы можем теперь записать его в несколько строк.
Доказательство (теоремы 1.5). Известно, что SU Т= U и множества S и Т не пересекаются, а потому ||S|| + ||7]| = ||£/||. Поскольку S— конечное множество, то ||5|| = п для некоторого целого числа п, а из того, что U — бесконечное множество, следует, что не существует такого целого числа р, для которого ||t/|| = р. Допустим, что множество Т— конечное, т.е. ||7]| = m для некоторого целого т. Тогда ||t/|| = ||S|| + ||7]| = т + п, что противоречит посылке — утверждению, что не существует целого числа, равного j| О
1.2.3. Другие формы теорем
Во многих разделах математики наиболее распространены теоремы вида «если-то». Однако приходится доказывать в виде теорем и другие типы утверждений. В этом разделе мы изучим основные схемы таких утверждений и способы их доказательств.
Разновидности утверждений типа „если-то»
Существует множество видов теорем, утверждения которых, на первый взгляд, отличаются от простого «если Я, то С», но на самом деле означают то же самое, а именно: если гипотеза Я верна при данном значении параметра (параметров), то при этом значении верно и заключение С. Вот несколько возможных способов записи утверждений типа «если Я, то С».
1. Я влечет С.
2. Я только тогда, когда С.
3. С, если Я.
4. Из Я следует С.
Форма 4 имеет множество разновидностей, например: «если Я, следовательно, С» или «если верно Я, то С также верно».
Пример 1.6. Утверждение теоремы 1.3 может быть записано в следующих четырех формах.
1. х > 4 влечет 2х > х2.
2. х > 4 только тогда, когда 2х > х2.
3. 2х > х2, если х > 4.
4. Из х > 4 следует 2х > х2.
Утверждения с кванторами
Во многих теоремах присутствуют утверждения с кванторами «для всех» и «существует» или их вариациями, например, «для каждого» вместо «для всех». От того, в каком порядке кванторы входят в утверждение, зависит его смысл. Часто оказывается полезным представлять утверждения с кванторами как «игру», в которой участвуют два игрока — «Для всех» и «Существует». Они по очереди определяют значения параметров теоремы. Игрок «Для всех» должен рассматривать все существующие возможности, поэтому параметры, на которые он действует, всегда остаются переменными. Игроку «Существует», напротив, достаточно выбрать лишь одно значение,
которое может зависеть от значений параметров, выбранных игроками ранее. Право первого хода определяется порядком вхождения кванторов в данное утверждение. Утверждение верно, если игрок, делающий ход последним, всегда может выбрать подходящее значение параметра.
В качестве примера рассмотрим альтернативное определение «бесконечного множества»: множество S бесконечно тогда и только тогда, когда для каждого целого числа п существует подмножество Т множества S, содержащее ровно п элементов. Здесь «Для каждого» предшествует «Существует», поэтому мы должны рассматривать произвольное целое п. Затем «Существует», используя информацию об п, выбирает подмножество Т. Так, если S— множество всех целых чисел, то «Существует» может выбрать подмножество Т= {1, 2, …, «}, удовлетворив таким образом требование независимо от п. Тем самым доказано, что множество целых чисел бесконечно. Следующее утверждение, похожее на определение бесконечного множества, некорректно, поскольку кванторы в него входят в обратном порядке: «существует подмножество Г множества S, при котором для всякого п множество Г содержит ровно п элементов». Теперь нам дано множество S, например множество целых чисел, и игрок «Существует» может выбрать произвольное его подмножество Т, например {1,2, 5}. Относительно данного множества «Для всех» должен доказать, что при любом п оно содержит п элементов. Но это невозможно, поскольку при п = 4, и вообще, для любого п Ф 3 это утверждение ложно.
В дополнение скажем, что в формальной логике вместо оборота «если-то» часто используется оператор —>. Таким образом, вместо выражения «если Н, то С» в математической литературе встречается запись Н —> С. Далее в книге этот оператор используется для других целей.
Утверждения типа „тогда и только тогда»
Иногда мы встречаемся с выражениями вида «А тогда и только тогда, когда В». Разновидностями этого утверждения являются «А эквивалентно В», «А равносильно В» или «А в точности тогда, когда В»1. На самом деле такое утверждение содержит два утверждения типа «если-то»: «если А, то В» и «если В, то А». Чтобы доказать, что «Л тогда и только тогда, когда Вп, необходимо доказать оба эти утверждения.
1. Достаточность (В для А), или «если»-часть: «если В, то А», т.е. «А тогда, когда В».
2. Необходимость (В для А), или «только-если»-часть: «если А, то В», т.е. «А только тогда, когда В».
‘В англоязычной математической литературе вместо выражения «if and only if’ часто используется его краткое обозначение — «iff’. Это утверждение еще называют эквивалентностью. — Прим. ред.
Какими должны быть формальные доказательства?
Ответить на этот вопрос не так просто. Все доказательства имеют одну цель — убедить кого-либо, будь то человек, проверяющий вашу работу, или вы сами, в корректности выбранной вами стратегии. Если доказательство убедительно, то этого вполне достаточно. Если же оно вызывает сомнения у «потребителя», значит оно недостаточно подробно.
Неопределенность в степени подробности доказательств обусловлена различными уровнями знаний у его возможного потребителя. Так, при доказательстве теоремы 1.4 мы предполагали, что читатель знает арифметику, и что такое утверждение, как «если у > 1, то у2 > 1», не вызовет у него сомнений. Если бы он не был знаком с арифметикой, то нам бы пришлось доказывать это утверждение и, соответственно, добавлять в наше дедуктивное доказательство несколько дополнительных пунктов. Существуют, однако, определенные требования к доказательству, которыми никак нельзя пренебрегать, иначе оно будет некорректным. Например, нельзя считать корректным дедуктивное доказательство, если оно содержит утверждение, не доказанное исходя из предыдущих или данных утверждений. Затем при доказательстве утверждений типа «тогда и только тогда» мы, конечно же, должны проводить их и в одну, и в другую сторону. Наконец, в индуктивных доказательствах (обсуждаемых в разделе 1.4) мы должны доказывать базисное утверждение и индуктивную часть.
Доказательство можно проводить в любом порядке. Во многих теоремах одна часть значительно проще другой. Обычно ее доказывают вначале, чтобы потом на нее не отвлекаться.
В формальной логике для обозначения утверждений типа «тогда и только тогда» встречаются операторы и Следовательно, запись А о В или А = В означает то же, что и «А тогда и только тогда, когда В».
Доказывая утверждения типа «тогда и только тогда», важно помнить, что следует доказывать обе его части — и необходимость, и достаточность. Иногда оказывается полезным разбить его на ряд нескольких эквивалентностей. Таким образом, чтобы доказать, что «А тогда и только тогда, когда В», вы можете вначале доказать что «А тогда и только тогда, когда С», а затем, что «С тогда и только тогда, когда В». Еще раз подчеркнем, что, применяя этот метод, обязательно нужно доказывать и необходимость, и достаточность. Доказав подобное утверждение лишь в одну сторону, мы тем самым оставляем доказательство незавершенным.
Приведем простой пример доказательства теоремы типа «тогда и только тогда». Введем следующие обозначения.
1. LxJ обозначает наибольшее целое число, меньшее или равное вещественному числу х.
2. Гх1 обозначает наименьшее целое число, которое больше или равно вещественному числу х. *
Теорема 1.7. Пусть х— вещественное число. LxJ = Гх~| тогда и только тогда, когда х — целое.
Доказательство. (Необходимость) В этой части мы предполагаем, что LxJ = Гх1, и попытаемся доказать, что х — целое число. Заметим, что по определению LxJ < х и Гх1 > х. Нам дано, что LxJ = Гх~|. Поэтому мы можем изменить в первом неравенстве LxJ на Гх1. Поскольку верны оба неравенства Гх1<х и Гх1>х, то согласно свойствам арифметических неравенств заключаем, что Гх~| = х. Поскольку число Гх1 всегда целое, х тоже целое.
(Достаточность) Предположим теперь, что х — целое, и попытаемся доказать, что LxJ = Гх»! Эта часть доказывается легко. По определению, LxJ и Гх1 при целом х оба равны х, а следовательно, равны между собой. □
1.2.4. Теоремы без гипотезы
Иногда встречаются теоремы, которые, на первый взгляд, не имеют гипотезы. Пример хорошо известен из тригонометрии. Теорема 1.8. sin2 в+ cos2 0 = 1. □
На самом деле у этой теоремы есть гипотеза, состоящая из тех утверждений, которые необходимо знать, чтобы понять смысл этого утверждения. В частности, здесь неявно предполагается, что 0 — это некоторый угол, и потому функции синус и косинус имеют обычный смысл. Исходя из определений членов этого равенства и теоремы Пифагора (в прямоугольном треугольнике квадрат гипотенузы равен сумме квадратов двух других сторон), вы можете доказать эту теорему. На самом деле, она имеет вид утверждения типа «если-то»: «если 0— угол, то sin2 0+ cos2 в — 1».

1.3. Дополнительные схемы доказательств
В этом разделе мы рассмотрим следующие дополнительные вопросы, касающиеся методов доказательств.
1. Доказательства утверждений о множествах.
2. Доказательства методом «от противного».
3. Доказательства с помощью контрпримера.
1.3.1. Доказательства эквивалентностей, связанных с множествами
В теории автоматов нам нередко приходится доказывать, что два множества, записанные разными способами, на самом деле равны. Часто эти множества состоят из цепочек символов и являются так называемыми «языками». Но в данном разделе природа множеств не будет играть роли. Если Е и F— выражения, представляющие некоторые множества, то утверждение Е = F означает, что эти множества равны. Точнее, каждый элемент множества, представленного Е, принадлежит множеству, представленному F, и наоборот.
Пример 1.9. Коммутативный закон объединения множеств утверждает, что, объединяя два множества, мы можем делать это в любом порядке, т.е. R[jS = S[j R. В данном случае в качестве Е выступает выражение R{JS, а в качестве F — S U R. Согласно коммутативному закону Е = F. □
Равенство Е = F можно переписать, как необходимое и достаточное условие: произвольный элемент х принадлежит множеству Е тогда и только тогда, когда х принадлежит F. Следовательно, доказательство для равенств множеств имеет такую же структуру, как и для утверждений типа «тогда и только тогда».
1. Доказать, что если х принадлежит Е, то х принадлежит и F.
2. Доказать, что если х принадлежит F, то х принадлежит и Е.
В качестве примера рассмотрим доказательство закона дистрибутивности объединения относительно пересечения.
Теорема 1.10. R U (S П Т) = (R U S) f| (R U Т).
Доказательство. Мы имеем дело со следующими выражениями: £ = /? U (S П 7) и
F=(/?US)n(tfU7).
Докажем по очереди обе части теоремы. Для доказательства необходимости предположим, что х принадлежит Е, и покажем, что тогда х принадлежит F. Эта часть доказательства представлена на рис. 1.5. При этом мы используем определения объединения и пересечения множеств, предполагая, что читатель с ними знаком.
Утверждение Обоснование
1. х принадлежит R U (S П Т) Посылка
2. х принадлежит R или х принадлежит S П (1) и определение объединения
3. х принадлежит R или х принадлежит как S, (1) и определение пересечения так и Т
4. х принадлежит R U S (3) и определение объединения
5. х принадлежит R U Т (3) и определение объединения
6. х принадлежит (R U S) П (R U Т) (4), (5) и определение пересечения
Рис. 1.5. Доказательство необходимости теоремы 1.10
Затем нужно доказать достаточность. Тут мы предполагаем, что х принадлежит F, и показываем, что тогда х принадлежит Е. Эта часть доказательства представлена на
рис. 1.6. Доказав обе части утверждения (и необходимость, и достаточность), мы тем самым доказали закон дистрибутивности объединения относительно пересечения. □
Утверждение
1. х принадлежит (R U S) П (R U Т)
(1) и определение пересечения
(1) и определение пересечения
4. х принадлежит R или х принадлежит как S, (2), (3) и рассуждения о множествах так и Т
(5) и определение объединения
5. х принадлежит R или х принадлежит S[\T (4) и определение пересечения
6. х принадлежит R U (S П Т)
Рис. 1.6. Доказательство достаточности теоремы 1.10
1.3.2. Контрапозиция
Всякое утверждение типа «если-то» может быть записано в эквивалентной форме, что подчас облегчает его доказательство. Утверждение «если не С, то не Я’ является обратным противоположному для утверждения «если Я, то С», или его контрапозицией. Утверждение и его контрапозиция либо оба истинны, либо оба ложны. Поэтому, доказав одно из них, мы доказываем и другое.
Чтобы показать, почему именно утверждения «если Я, то С» и «если не С, то не Я» логически равносильны, рассмотрим следующие четыре случая.
Я и С оба истинны.
Я истинно, а Сложно.
Обоснование
Посылка
2. х принадлежит R U S
3. х принадлежит R U Т
С истинно, а Я ложно.
ЯиСобаложны.
Тогда и только тогда» для множеств
Как мы уже упоминали, теоремы, которые устанавливают эквивалентность выражений для множеств, являются утверждениями типа «тогда и только тогда». Таким образом, утверждение теоремы 1.10 может быть записано в виде: «элемент х принадлежит R U (S П Т) тогда и только тогда, когда х принадлежит (R U S) П (R U 7)».

Эквивалентность множеств можно выразить иначе с помощью оборота «все те, и только те». Например, утверждение теоремы 1.10 может быть записано в таком виде: «элементами множества R U (Sfl 7) являются все те, и только те элементы, которые принадлежат (R U S) П (R U 7)».
Утверждение типа «если-то» может быть ложным лишь в одном случае — когда гипотеза истинна, а заключение ложно, что соответствует случаю (2). В остальных трех случаях, включая и случай (4), в котором заключение ложно, данное утверждение типа «если-то» остается истинным.
Теперь рассмотрим, когда ложно утверждение, обратное противоположному, т.е. «если не С, то не Я’. Для того чтобы это утверждение было ложным, его гипотеза («не С») должна быть истинной, а заключение («не Я’) —- ложным. Но «не С» истинно именно тогда, когда С— ложно, а «не Я’ ложно именно тогда, когда Я— истинно. А это и есть случай (2). Последнее означает, что в каждом из четырех возможных случаев утверждение и его контрапозиция одновременно либо истинны, либо ложны, т.е. они логически эквивалентны.
Обратное утверждение (конверсия)
Не следует путать понятия «утверждение, обратное противоположному» (контрапозиция) и «обратное утверждение» (конверсия). Конверсия утверждения типа «если-то» (или обратное утверждение) есть то же утверждение, прочитанное «в обратную сторону». Следовательно, конверсией утверждения «если Я, то С» является утверждение «если С, то Я’. В отличие от контрапозиции, конверсия не является логически эквивалентной исходному утверждению. На самом деле, части утверждения типа «тогда и только тогда» всегда представляют собой некоторое утверждение и его конверсию.
Пример 1.11. Вспомним теорему 1.3, в которой утверждалось: «если х>4, то 2х > х2». Для данного утверждения обратное противоположному есть: «если не 2х >х2, то не х > 4». Говоря обычным языком и приняв во внимание, что «не а > Ъ» означает а < Ь, можно записать эту контрапозицию таким образом: «если 2х <х2, то.г < 4». □
Использование контрапозиции при доказательстве теорем типа «тогда и только тогда» дает нам несколько дополнительных возможностей. Представьте, например, что необходимо доказать эквивалентность множеств Е- F. Тогда в утверждении «х принадлежит Е тогда и только тогда, когда х принадлежит F’ мы можем одну из частей заменить ее кон- трапозицией. Одна из возможных форм такова.
• Если х принадлежит Е, то х принадлежит F, а если х не принадлежит £, то х не принадлежит F.
В последнем утверждении £ и F можно также поменять местами.
1.3.3. Доказательство методом „от противного»
Еще один способ доказать утверждение типа «если-то» состоит в том, чтобы доказать утверждение
• «Я и не С влечет ложь».
Следовательно, следует вначале предположить, что верны гипотеза Я и отрицание заключения С. Затем нужно доказать, что из Я и «не С» следует некоторое заведомо ложное утверждение. Эта схема доказательства называется доказательством «от противного».
Пример 1.12. Вспомним теорему 1.5, в которой было доказано утверждение типа «если-то» с гипотезой H = «U— бесконечное множество, S— конечное подмножество U, Т— дополнение S относительно U» и заключением С = «Т— бесконечное множество». Мы доказывали эту теорему методом «от противного»: предполагая «не С», т.е., что Т— конечное множество, пытались вывести некоторое ложное утверждение. Мы показали, что если S и Т— оба конечны, то и U должно быть конечным. Но, поскольку согласно гипотезе Я U— бесконечное множество, и быть одновременно конечным и бесконечным множество не может, то полученное утверждение ложно. Выражаясь терминами логики, мы имеем некоторое утверждение р {U— конечно) и его отрицание «не р» (U — бесконечно). Затем используем тот факт, что утверждение «р и не р» всегда ложно. □
Обоснуем теперь корректность метода доказательства «от противного» с точки зрения логики. Вспомним раздел 1.3.2, где мы показали, что из четырех возможных комбинаций значений истинности Я и С только во втором случае утверждение «если Я, то С» ложно. Из ложности Я и не С следует, что случай 2 невозможен. Таким образом, возможны лишь оставшиеся три комбинации, и для каждой из них утверждение «если Я, то С» истинно.
1.3.4. Контрпримеры
В обыденной жизни нам не приходится доказывать теорем. Однако довольно часто мы сталкиваемся с чем-то, что кажется нам верным — например, со стратегией реализации программы, и мы вынуждены задумывается над истинностью такого рода «теоремы». Чтобы решить эту проблему, можно попытаться сначала доказать ее истинность, а если это ие удастся, то обосновать ее ложность.
Теоремы, вообще говоря, являются утверждениями, включающими бесконечное число случаев, соответствующих множеству значений входящих в них параметров. В математике существует строгое соглашение о том, что утверждение можно назвать «теоремой» лишь тогда, когда оно описывает бесконечное число случаев. Те же утверждения, в которые параметры либо вовсе не входят, либо они могут принимать лишь конечное число значений, называют наблюдениями. Для того чтобы доказать, что предполагаемая теорема неверна, достаточно показать, что она ложна хотя бы в одном случае.
Схожая ситуация имеет место и с программами, поскольку мы обычно считаем, что программа содержит ошибку, если она неверно обрабатывает хотя бы один набор входных данных, с которым она должна работать.
Часто бывает легче доказать, что утверждение не является теоремой, чем доказать, что оно — теорема. Мы уже упоминали о том, что, если S— некоторое утверждение, то утверждение «S — не теорема» само по себе уже не содержит параметров, а потому является наблюдением, а не теоремой.
В следующих двух примерах первое утверждение, очевидно, не является теоремой, а второе лишь похоже на теорему, однако требуется некоторое дополнительное исследование, чтобы доказать, что оно — не теорема.
Мннмая теорема 1.13. Все простые числа нечетны. (Более строго: если целое число х является простым, то х — число нечетное.)
Опровержение. 2 — простое число, но 2 четно. □
Обсудим теперь «теорему», в которой используются элементы арифметической теории делимости. Но сначала дадим следующее важное определение.
Если а и b — натуральные числа, то a mod b — это остаток от деления а на Ь, т.е. такое целое число г между 0 и b — 1, что а = qb + г, где q — некоторое целое число. Например, 8 mod 3 = 2, а 9 mod 3=0. Докажем, что следующая теорема неверна.
Мнимая теорема 1.14. Не существует такой пары целых чисел а и Ь, для которой a mod b — b mod a. □
Оперируя парами объектов, как а и 6 в данном случае, мы зачастую можем упростить отношения между объектами, используя симметричность. Так, мы можем подробно рассмотреть лишь случай а < Ь, поскольку если а > Ь, то а и b можно просто поменять местами. При этом в теореме 1.14 получим то же равенство. Но необходимо быть осторожным и не забыть о третьем случае, когда а = Ь. Именно здесь кроется подвох в попытке доказательства теоремы.
Итак, предположим, что а < Ь. Тогда a mod b = а, поскольку в определении остатка a mod b для этого случая имеем q = 0 и г — а, т.е. а = 0 х b + а, когда а < Ь. Но b mod а<а, так как любой остаток от деления на а есть число между 0 и а — 1. Таким образом, если а < Ь, то b mod а<а mod b, так что равенство a mod b = b mod а невозможно. Используя теперь приведенные выше рассуждения о симметричности, получаем, что a mod b Ф b mod айв случае, когда b < а.
Однако есть еще третий случай, когда а = Ь. Поскольку для любого целого х выполнено х mod х = 0, то при а = b имеем a mod b = b mod а. Этим предполагаемая теорема опровергнута.
Опровержение мннмон теоремы 1.14. Пусть а = b — 2, тогда a mod b = b mod a = 0. □
В процессе поиска контрпримера мы на самом деле нашли точные условия, при выполнении которых предполагаемая теорема верна. Ниже приведена правильная формулировка этой теоремы и ее доказательство.
Теорема 1.15. a mod 6 = 6 mod а тогда и только тогда, когда а = Ь. Доказательство. (Достаточность) Предположим, что а = Ь. Тогда, как было отмечено выше, х mod х = 0 для любого целого х. Таким образом, a mod b = b mod a = 0, если a = b.
(Необходимость) Предположим теперь, что a mod 6 = 6 mod а. Лучше всего в данном случае применить метод «от противного», и предположить, что заключение неверно, т.е. что аФ Ь. Тогда, поскольку вариант а = 6 исключается, остается рассмотреть случаи а < 6 и 6 < а.
Выше мы выяснили, что если а < 6, то a mod 6 = а и 6 mod а < а. Эти утверждения совместно с гипотезой a mod 6=6 mod а приводят к противоречию. По свойству симметричности, если 6 < а, то 6 mod а = 6 и a mod 6 < 6. Снова получаем противоречие. Таким образом, необходимость также доказана. Итак, теорема верна, поскольку мы доказали ее в обе стороны.
1.4. Индуктивные доказательства
При оперировании с рекурсивно определенными объектами мы сталкиваемся с необходимостью использовать в доказательствах особый метод, называемый «индуктивным». Большинство известных индуктивных доказательств оперирует с целыми числами, но в теории автоматов нам приходится индуктивно доказывать утверждения о таких рекурсивно определяемых понятиях, как деревья и разного рода выражения, например, регулярные, о которых мы уже вкратце упоминали в разделе 1.1.2. В этом разделе будут рассмотрены индуктивные доказательства сначала на примере «простых» индукций для целых чисел. Затем мы покажем, как проводить «структурную» индукцию для любых рекурсивно определяемых понятий.
1.4.1. Индукция по целым числам
Пусть требуется доказать некое утверждение S(n), которое зависит от целого числа п. Существует общий подход к доказательствам такого рода. Доказательство разбивается на следующие два этапа.
1. Базис. На этом этапе мы показываем, что S(i) верно для некоторого частного целого значения /. Обычно полагают / = 0 или /= 1, но существуют примеры, где выбирается большее начальное значение, например, когда для всех меньших значений / утверждение S ложно.
2. Индуктивный переход. Здесь мы предполагаем, что п > г, где i— целое число из базиса индукции, и доказываем, что из истинности S(n) следует истинность S(n + 1), т.е. доказываем утверждение «если S(n), то S(n + 1)».
На уровне здравого смысла данное доказательство убеждает нас в том, что S(n) на самом деле верно для всякого целого п, большего или равного базисному /. Обосновать это можно следующим образом. Предположим, что 5(л) ложно для одного или нескольких таких целых п. Тогда среди этих значений п существует наименьшее, скажем,у, причем j > i. Значение j не может быть равным i, так как на основании базиса индукции 5(0 истинно. Поэтому j должно быть строго больше i. Таким образом, мы знаем, что j — 1 > i и S(j- 1) истинно.
Но во второй части доказательства показано, что если п > i, то S(n) влечет S(n + 1). Предположим, что n=j- 1. Тогда, совершая индуктивный переход, из S(j — 1) выводим S(j). Следовательно, из истинности S(j- 1) следует истинность S(j).
Но мы предполагали, что справедливо отрицание доказываемого утверждения, а именно: 5(/) ложно для некоторого j > i. Придя к противоречию, мы тем самым доказали методом «от противного», что 5(и) истинно для всех п > i.
К сожалению, в приведенных рассуждениях присутствует трудноуловимый логический изъян. Дело в том, что первый пункт нашего предположения о том, что мы можем выбрать наименьшее j > i, для которого S(j) ложно, зависит от того, принимаем ли мы на веру справедливость принципа индукции. Это значит, что по сути единственный способ доказать существование такого j есть индуктивное доказательство. Но с позиций здравого смысла приведенное нами «доказательство» вполне осмысленно, и соответствует нашему пониманию мира. В связи с этим мы присоединим к нашей логической системе следующий закон.
• Принцип индукции: если доказано, что 5(0 верно, и что при всех п > i из S(n) следует 5(и + 1), значит, 5(л) истинно при всех п > /’.
Покажем на следующих двух примерах, как принцип индукции используется при доказательстве теорем о целых числах. Теорема 1.16. Для всех п > 0
jjy = «(«+ 1Х2Я + 1) (1 ]}
i=i 6
Доказательство. Доказательство будет состоять из двух частей: базиса и индуктивного шага. Докажем их по очереди.
Базис. В качестве базисного значения выберем п = 0. В левой части равенства (1.1)
о
стоит ^ , поэтому может показаться, что при п — 0 утверждение теоремы не имеет
смысла. Однако существует общий принцип, согласно которому, если верхний предел
суммы (в данном случае 0) меньше нижнего предела (здесь 1), то сумма не содержит
о
слагаемых и равна 0. Это значит, что X’2 = ® •
1
Правая часть равенства (1.1) также равна нулю, поскольку 0х(0 + 1)х(2х0 + 1)/6 = 0. Таким образом, при п = 0 равенство (1.1) выполняется.
Индукция. Предположим теперь, что п > 0. Мы должны совершить индуктивный переход, т.е. доказать, что, изменив в равенстве (1.1) п на п+ 1, мы получим также правильное соотношение. Оно имеет следующий вид.
= [п + Жп + \} + \)(2[п + !] + !) (^ 2)
,=i 6
Можно упростить равенства (1.1) и (1.2), раскрыв скобки в правых частях. Равенства примут следующий вид.
jS2 =(2и3+Зи2+я)/6 (1.3)
<=1
в+1
£/2 =(2w3+9«2+13« + 6)/6 (1.4)
/=1
Нам нужно доказать (1.4), используя (1.3). Эти равенства соответствуют утверждениям S(n + 1) и S(n) из принципа индукции. «Фокус» заключается в том, чтобы разбить сумму для п + 1 в левой части (1.4) на сумму для п плюс (я + 1)-й член. После чего мы сможем убедиться, что (1.4) верно, заменив сумму первых п членов левой частью равенства (1.3). Запишем эти действия.
£/2 +(я + 1)2 =(2я3+9л2+13я + 6)/6 (1.5)
J=l )
(2 п3 + Ъп2 + «)/6 + (п2 + 2п +1) = (2я3 + 9w2 +1 Ъп + 6)/6 (1.6)
Наконец, чтобы убедиться в справедливости (1.6), нужно преобразовать левую часть этого равенства в правую с помощью несложных алгебраических действий. □
Пример 1.17. В этом примере мы докажем теорему 1.3 из пункта 1.2.1. Напомним, в этой теореме утверждается следующее: если х > 4, то 2х > х2. Мы уже приводили неформальное доказательство этой теоремы, основной идеей которого являлось то, что отношение х2/2х уменьшается с ростом х, когда х > 4. Мы придадим строгость нашим рассуждениям, доказав утверждение 2*>;с2 по индукции, начиная с базисного значения х = 4. Отметим, кстати, что при х < 4 утверждение неверно.
Базис. Если х = 4, то и 2х, и х2 равны 16. Следовательно, нестрогое неравенство 2х > х выполнено.
Индукция. Предположим, что 2х > х2 для некоторого х>4. Приняв это утверждение в качестве гипотезы, мы должны доказать, что верно и следующее утверждение 2ix+r> >(х+ I)2, где вместо х стоит х+ 1. Эти два утверждения соответствуют S(x) и S(x + 1) в принципе индукции. Тот факт, что мы в качестве параметра используем не п, а х, не имеет значения, это всего лишь обозначение локальной переменной.
Как и в теореме 1.16, мы должны переписать S(x + 1) так, чтобы можно было использовать S(x). В данном случае мы можем записать 2<х+>> как 2×2*. S(x) утверждает, что 2х > х2, поэтому можно заключить, что 2Х+1 = 2×2х > 2х2.
Но нам нужно показать нечто иное, а именно: 2(х+>) > (х + I)2. Это можно сделать, доказав, например, что 2х2 > (х + I)2, а затем, использовав транзитивность отношения >, показать, что 2(r+1) > 2х2> (х + 1)2. Доказывая, что
2×2>(X+ I)2, (1.7)
можно использовать предположение, что х > 4. Для начала упростим (1.7):
х2>2*+1. (1.8)
Разделив обе части (1.8) на х, получим:
х>2 + ~. (1.9)
х
Поскольку х > 4, то \/х < 1/4. Таким образом, минимальное значение выражения в левой части (1.9) равно 4, а максимальное значение выражения в правой— 2.25. Итак, истинность (1.9) доказана. Следовательно, верны (1.8) и (1.7). В свою очередь, (1.7) влечет 2х2> (х + I)2 при х > 4, что позволяет доказать утверждение S(x + 1), т.е. 2x+l > (х + I)2. □
Целые числа как рекурсивно определяемые понятия
Мы уже упоминали о том, что индуктивные доказательства особенно полезны при работе с рекурсивно определяемыми объектами. Но в первых же примерах мы столкнулись с индукцией по целым числам, которые нами, как правило, не воспринимаются как объекты, определяемые рекурсивно. Однако существует естественное рекурсивное определение неотрицательного целого числа. Это определение вполне соответствует индуктивной процедуре по целым числам: переходу от ранее определенных объектов к тем, что определяются позже. Базис. О есть целое число.
Индукция. Если п — целое число, то п + 1 — тоже целое число.

1.4.2. Более общие формы целочисленных индуктивных доказательств
В разделе 1.4.1 мы описали схему индуктивного доказательства по целым числам, где утверждение 5 доказывается вначале для некоторого базисного значения, а затем доказывается «если S(n), то S(n + 1)». Однако иногда индуктивное доказательство возможно лишь при использовании более общих схем. Рассмотрим следующие два важных обобщения.
1. Можно использовать несколько базисных значений. Это значит, что мы доказываем 5(0, 5(/ + 1),…, S(j) для некоторого j > /’.
2. При доказательстве S(n + 1) можно использовать истинность не только S(n), но также и всех утверждений S(i), S(i+ 1), …, S(n). Кроме того, если доказана истинность S для базисных значений вплоть до j, то можно предполагать не только п > /’, но и п > j. На основании доказательств такого базиса и индуктивного шага можно заключить, что S(n) истинно для всех п > i.
Пример 1.18. Возможности обоих описанных выше принципов проиллюстрируем на примере следующего утверждения S(n): «если п > 8, то п можно представить в виде суммы троек и пятерок». Отметим, между прочим, что 7 нельзя представить в таком виде.
Базис. В качестве базисных утверждений выберем S(8), S(9) и S(10). Доказательства их соответственно таковы: 8 = 3 + 5, 9 = 3 + 3 + Зи10 = 5 + 5.
Индукция. Предположим, что п> 10 и S(8), S(9), …, S(n) истинны. Используя эти факты, мы должны доказать, что истинно S(n + 1). Для этого вычтем сначала 3 из rt + 1, заметим, что полученная разность должна быть представима в виде суммы троек и пятерок, а затем прибавим к этой сумме 3 и получим сумму для п + 1.
Более строго вышесказанное выглядит так. Поскольку п — 2 > 8, то можно сделать предположение об истинности S(n — 2), т.е. и — 2 = За + 56 для некоторых целых а и 6. Но тогда /7+1 = 3 + За + 56, и, значит, мы можем записать п + 1 в виде суммы а + 1 троек и Ь пятерок. Это позволяет нам завершить индуктивный шаг и доказывает истинность утверждения S(n + 1). □

1.4.3. Структурная индукция
В теории автоматов используется несколько рекурсивно определяемых понятий, относительно которых нам будет необходимо доказывать те или иные утверждения. Важными примерами таких понятий являются деревья и выражения. Подобно индукции, все рекурсивные определения включают базис, где определяется одна или несколько элементарных структур, и индуктивный шаг, с помощью которого более сложные структуры определяются через структуры, определенные ранее.
Пример 1.19. Рассмотрим рекурсивное определение дерева. Базис. Одиночный узел есть дерево, и этот узел является корнем дерева. Индукция. Если Т,, Т2, …. Тк — деревья, то можно построить новое дерево следующим образом.
1. Возьмем в качестве корня новый узел N.
2. Возьмем по одному экземпляру деревьев Т,, Т2,…, 7^.
3. Добавим ребра, соединяющие корень N, с корнями каждого из деревьев 7/, Т2, …, 7^. Индуктивное построение дерева с корнем N из к меньших деревьев представлено на рис. 1.7. □
Пример 1.20. Определим рекурсивно понятие выражения, использующего арифметические операции + и *. В качестве его операндов могут выступать как числа, так и переменные.
Базис. Всякое число или буква (т.е. переменная) есть выражение. Индукция. Пусть Е и F— некоторые выражения, тогда Е + F, Е * F и (£) также являются выражениями.
Например, 2 и х являются выражениями согласно базису. Индуктивный шаг позволяет утверждать, что х + 2, (г + 2) и 2*(х +2) — тоже выражения. Отметим, что каждое из них состоит из частей, в свою очередь являющихся выражениями. О

Неформальное обоснование структурной индукции
Можно неформально обосновать правомочность структурной индукции как метода доказательства. Представим, что в процессе рекурсивного определения мы последовательно вводим некоторые структуры X,, Х2, …. Первыми в этой последовательности идут базисные элементы, и структура X, определена, если только все ее подструктуры предшествуют^ в этой последовательности. С этой точки зрения структурная индукция — ни что иное, как обычная индукция по п для утверждения S(Xn). В частности, это может быть и обобщенная индукция, описанная в разделе 1.4.2, т.е. в ней могут использоваться базисные утверждения, а индуктивный переход может опираться на все предыдущие утверждения. Однако следует помнить, что, как и в разделе 1.4.1, данное апеллирующее к интуиции пояснение не является формальным доказательством. Фактически, мы должны допустить справедливость этого принципа, так же, как в том разделе допустили справедливость исходного принципа индукции.
Если у нас имеется рекурсивное определение некоторого понятия, то теоремы относительно этого понятия можно доказывать с помощью следующего метода, называемого структурной индукцией. Пусть S(X) — утверждение о структурах X, определяемых рекурсивно.

1. В качестве базиса докажем утверждение S(X) для базисной структуры (или структур)^.
2. Для индуктивного перехода возьмем структуру X, определенную рекурсивно через Yh Y2, …, Yk. Предполагая, что верны утверждения S(Y,), S(Y2), …, S(Kk), докажем с их помощью S(X).
Отсюда заключаем, что S(X) истинно для всех X. В следующих двух примерах мы доказываем теоремы о деревьях и выражениях.
Теорема 1.21. В любом дереве число узлов на единицу больше числа ребер.
Доказательство. Запишем утверждение S(T), которое нам требуется доказать методом структурной индукции в формальном виде: «Если Т— дерево, и Т содержит п узлов и е ребер, то п = е + 1».
Базис. В качестве базисного выберем случай, когда дерево Т состоит из одного узла. Тогда п = 1 и е = 0, а потому соотношение п — е + 1 выполнено.
Индукция. Пусть Т— дерево, построенное по индуктивному определению из корневого узла N п к меньших деревьев Г/, Т2, …, Гк. Предположим, что утверждение S(T) истинно при i= 1,2,…, к, т.е., если дерево Т, содержит п, узлов и ех ребер, то п, = е,+ 1.
Узлы дерева Т— это узел N и все узлы деревьев 7]. Таким образом, Т содержит 1 + п, + п2 + … + «к узлов. Ребра Т— это к ребер, которые мы добавили на индуктивном шаге определения, плюс все ребра деревьев 7]. Значит, Т содержит
к + е, + е2 + … + ек (1.10)
ребер. Заменив щ на е\ + 1 в выражении для числа узлов Т, получим, что оно равно
1 + [е,+ \] + [е2+1] + … + [ек+ 1]. (1.11)
Поскольку в сумме (1.11) содержится к слагаемых вида «+1», ее можно перегруппировать таким образом.
к+ 1 + ei + e2+ … + ек (1.12)
Это выражение равно на единицу больше, чем значение выражения (1.10), показывающего число ребер Т. Таким образом, число узлов на единицу больше числа ребер. □
Теорема 1.22. Всякое выражение содержит поровну правых и левых скобок.
Доказательство. Говоря формально, необходимо доказать такое утверждение S(G) относительно выражения G, определенного рекурсивно в примере 1.20: левых и правых скобок в G поровну.
Базис. Если G — базисное выражение, то это либо число, либо переменная. В этих выражениях 0 левых и 0 правых скобок, т.е. поровну.
Индукция. По определению индуктивного шага существует три способа построения выражения G.
1. G = Е + F.
2. G = E*F.
3. G — (£).
Мы предполагаем, что утверждения S(E) и S(F) истинны, т.е. что каждое из выражений Е и F содержит поровну правых и левых скобок, по и и и, соответственно. Тогда в каждом из трех случаев мы можем подсчитать число входящих в G правых и левых скобок.

1. Если G = Е + F, то G содержит по п + т скобок каждого сорта: по п левых и правых скобок из выражения Е, и по т — из F.
2. Если G = Е * F, то G также содержит по п + т скобок каждого сорта, как и в случае (1).
3. Если же G = (£), то G содержит п + 1 левых скобок — одну мы видим явно, а п находятся в Е. Аналогично G содержит п + 1 правых скобок (одна явная и п в Е).
Итак, в каждом из этих трех случаев число правых и левых скобок в G одинаково, а это значит, что теорема доказана.
1.4.4. Совместная индукция
Иногда мы не можем доказать по индукции некоторое отдельно взятое утверждение, и вместо этого нам нужно доказать совместно целую группу утверждений S,(ri), S2(n),…, Sk(/j) с помощью индукции по п. В теории автоматов такая ситуация встречается довольно часто. Так, в примере 1.23 мы рассмотрим общую ситуацию, в которой действие автомата описывается группой утверждений, по одному для каждого из состояний. В этих утверждениях говорится, какие последовательности входных сигналов приводят автомат в каждое из его состояний.
Строго говоря, доказательство группы утверждений не отличается от доказательства конъюнкции (логическое «И») всех этих утверждений. Например, группу утверждений Si(n), S2(n),…, Sk(n) можно заменить одним утверждением St(n) И S2(n) И … И Sk(n). Однако, если необходимо доказывать несколько действительно независимых утверждений, то проще рассматривать их отдельно и для каждого из них доказывать свой базис и индуктивный шаг. Этот тип доказательства назовем совместной индукцией. В следующем примере мы покажем, какие основные этапы должно содержать такое доказательство.
Пример 1.23. Вернемся к примеру 1.1, где в виде автомата был представлен переключатель состояний «вкл.-выкл.». Сам автомат еще раз воспроизведен на рис. 1.8. Нажатие кнопки переводит автомат из одного состояния в другое, а в качестве начального выбрано состояние «выкл.», поэтому можно предполагать, что поведение переключателя описывается системой из следующих двух утверждений.
S/(n): после n нажатий кнопки автомат находится в состоянии «выкл.» тогда и только тогда, когда п — четное число.
S2(n): после п нажатий кнопки автомат находится в состоянии «вкл.» тогда и только тогда, когда п — нечетное число.
Нажатие

Рис. 1.8. Повтор автомата с рис. 1.1

Поскольку число п не может быть одновременно и четным, и нечетным, то можно предположить, что из St следует S2, и наоборот. Однако, вообще говоря, то, что некоторый автомат находится в одном и только в одном состоянии, не всегда верно. На самом деле автомат на рис. 1.8 находится всегда лишь в одном из состояний, но этот факт нужно доказывать как часть совместной индукции.
Ниже приводятся доказательства базисов и индуктивных шагов для утверждений St(n) и S2(n). В доказательствах используются некоторые свойства четных и нечетных чисел, а именно: если к четному числу прибавить 1 или вычесть из него 1, то получим число нечетное, а если то же самое проделать с нечетным числом, то получим четное.

Базис. В качестве базисного значения выберем п = 0. Поскольку требуется доказать два утверждения типа «тогда и только тогда», причем каждое из них в обе стороны, то фактически нужно рассмотреть четыре базисных случая и четыре шага индукции.
1. [Si~, достаточность] Поскольку 0 — четное число, мы должны показать, что после 0 нажатий автомат на рис. 1.8 находится в состоянии «выкл.». Но это действительно так, поскольку начальное состояние автомата — «выкл.».
2. [5/; необходимость] После 0 нажатий автомат находится в состоянии «выкл», поэтому нам нужно показать, что 0 — четное число. Но тут и доказывать нечего, поскольку 0 есть четное число по определению.
3. достаточность] Гипотеза достаточности S2 состоит в том, что 0— нечетное число. Очевидно, она ложна. А поскольку гипотеза //ложна, то, как показано в разделе 1.3.2, всякое утверждение вида «если //, то С» истинно. Таким образом, и эта часть базиса верна.
4. необходимость] Гипотеза о том, что после 0 нажатий автомат находится в состоянии «вкл.» также ложна, так как в это состояние мы попадаем только по стрелке «Нажатие», а это означает, что на кнопку нажали хотя бы один раз. Отсюда, как и
ранее, приходим к выводу, что утверждение типа «если-то» истинно, поскольку его гипотеза ложна.
Индукция. Предположим теперь, что Si(n) и S2(n) истинны, и докажем утверждения Si(n + 1) и S2(n + 1). Это доказательство также разделяется на следующие четыре части.

1. [Si(n+ 1); достаточность] Гипотезой для этой части является то, что п+ 1 — четное число, т.е. п — нечетное. В этом случае из достаточности утверждения S2(n) следует, что после п нажатий автомат находится в состоянии «вкл.». Дуга из «вкл.» в «выкл», обозначенная сигналом «Нажатие», указывает, что (п + 1)-е нажатие переводит автомат в состояние «выкл.». Таким образом, доказана достаточность утверждения Si.
2. [S/и + 1); необходимость] Предположим, что после (п + 1 )-го нажатия автомат находится в состоянии «выкл». Тогда, анализируя автомат на рис. 1.8, можно сделать вывод, что в состояние «выкл.» мы попадаем, находясь в состоянии «вкл.» и получая на вход «Нажатие». Таким образом, если после (п + 1)-го нажатия мы находимся в состоянии «выкл», то после п нажатий мы находились в состоянии «вкл.». Но тогда из необходимости утверждения S2(n) заключаем, что п — нечетное число. Следовательно, п + 1 — число четное, а это и есть нужное нам заключение «необходимости» в утверждении Si(n + 1).
3. [S2(n + 1); достаточность] Для доказательства этой части достаточно в пункте (1) поменять местами утверждения S2 и St, а также слова «четное» и «нечетное». Не сомневаемся, что читатель самостоятельно восстановит это доказательство.
4. [S/n+l); необходимость] Для этого доказательства достаточно в п. 2 поменять
местами S2 и Sh а также «нечетное» и «четное». □
На основе примера 1.23 можно сделать следующие общие выводы относительно совместных индуктивных доказательств.
• Для каждого утверждения нужно отдельно доказать и базис, и индуктивный шаг.
• Если утверждения имеют вид «тогда и только тогда», то при доказательстве и базиса, и шага индукции утверждения нужно доказывать в обе стороны.

1.5. Основные понятия теории автоматов
В этом разделе вводятся наиболее важные из понятий, которыми оперирует теория автоматов: «алфавит» (множество символов), «цепочка» (последовательность символов некоторого алфавита) и «язык» (множество цепочек в одном и том же алфавите).
1.5.1. Алфавиты
Алфавитом называют конечное непустое множество символов. Условимся обозначать алфавиты символом Наиболее часто используются следующие алфавиты.
1. £ = {0,1} — бинарный или двоичный алфавит.
2. £ = {а, Ь, …, z} — множество строчных букв английского алфавита.
3. Множество ASCII-символов или множество всех печатных ASCII-символов.
1.5.2. Цепочки
Цепочка, или иногда слово, — это конечная последовательность символов некоторого алфавита. Например, 01101 — это цепочка в бинарном алфавите £ = {0, 1}. Цепочка 111 также является цепочкой в этом алфавите.
Пустая цепочка
Пустая цепочка— это цепочка, не содержащая ни одного символа. Эту цепочку, обозначаемую е, можно рассматривать как цепочку в любом алфавите.
Длина цепочки
Часто оказывается удобным классифицировать цепочки по их длине, т.е. по числу позиций для символов в цепочке. Например, цепочка 01101 имеет длину 5. Обычно говорят, что длина цепочки — это «число символов» в ней. Это определение широко распространено, но не вполне корректно. Так, в цепочке 01101 всего 2 символа, но число позиций в ней — пять, поэтому она имеет длину 5. Все же следует иметь в виду, что часто пишут «число символов», имея в виду «число позиций».
Длину некоторой цепочки w обычно обозначают |w|. Например, |011| = 3, а |е| = 0.
Степени алфавита
Если Z — некоторый алфавит, то можно выразить множество всех цепочек определенной длины, состоящих из символов данного алфавита, используя знак степени. Определим как множество всех цепочек длины к, состоящих из символов алфавита Z.
Пример 1.24. Заметим, что = {е} независимо от алфавита Е, т.е. е— единственная цепочка длины 0.
Если X = {0, 1}, то Е1 = {0, 1}, Z2= {00, 01, 10, 11}, Z3 = {000, 001, 010, 011, 100, 101, 110, 111} и так далее. Отметим, что между Z и X’ есть небольшое различие. Дело в том, что 2 есть алфавит, и его элементы 0 и 1 являются символами, а Е1 является множеством цепочек, и его элементы — это цепочки 0 и 1, каждая длиной 1. Мы не будем вводить разные обозначения для этих множеств, полагая, что из контекста будет понятно, является {0, 1} или подобное ему множество алфавитом или же множеством цепочек. □
Соглашения о символах и цепочках
Как правило, строчными буквами из начальной части алфавита (или цифрами) мы будем обозначать символы, а строчными буквами из конца алфавита, например w, х, у или z — цепочки. Руководствуясь этим соглашением, вы легко сможете понять, элементы какого типа рассматриваются в том или ином случае.
Множество всех цепочек над алфавитом 2 принято обозначать 2*. Так, например, {0,1}* = {в, 0, 1, 00, 01, 10, 11, 000,…}. По-другому это множество можно записать в виде
2 =2°U2′ U£ U…
Иногда нам будет необходимо исключать из множества цепочек пустую цепочку. Множество всех непустых цепочек в алфавите 2 обозначают через 2+. Таким образом, имеют место следующие равенства:
• 2+ = 21 U 22 U 23 U …
• 2*=2+U{£}.
Конкантенация цепочек
Пусть х и у— цепочки. Тогда ху обозначает их конкатенацию (соединение), т.е. цепочку, в которой последовательно записаны цепочки х и у. Более строго, если х — цепочка из / символов: х = a/a2…aj, а у— цепочка из j символов: у = b,b2…bj, то ху— это цепочка длины i+j:xy = а,а2…аф,Ь2…Ьу
Пример 1.25. Пусть х = 01101 и у= 110. Тогда ху = 01101110, а ух= 11001101. Для любой цепочки w справедливы равенства ew = we = w. Таким образом, е является единицей (нейтральным элементом) относительно операции конкантенации, поскольку результат ее конкатенации с любой цепочкой дает ту же самую цепочку (аналогично тому как 0, нейтральный элемент относительно сложения, при сложении с любым числом х дает число х). □
1.5.3. Языки
Множество цепочек, каждая из которых принадлежит 2*, где 2 — некоторый фиксированный алфавит, называют языком2. Если 2 — алфавит, и L с 2*, то L — это язык над 2, или в 2. Отметим, что язык в 2 не обязательно должен содержать цепочки, в которые входят все символы 2. Поэтому, если известно, что L является языком в 2, то можно утверждать, что L — это язык над любым алфавитом, содержащим 2.
Термин «язык» может показаться странным. Однако оправданием служит то, что и обычные языки можно рассматривать как множества цепочек. Возьмем в качестве примера английский язык, где набор всех литературных английских слов есть множество цепочек в алфавите (английских же букв). Еще один пример — язык программирования С или любой другой язык программирования, в котором правильно написанные программы представляют собой подмножество множества всех возможных цепочек, а цепочки состоят из символов алфавита данного языка. Этот алфавит является подмножеством символов ASCII. Алфавиты для разных языков программирования могут быть различными, хотя обычно они состоят из прописных и строчных букв, цифр, знаков пунктуации и математических символов.

Существует, однако, множество других языков, изучаемых в теории автоматов. Приведем несколько примеров.
1. Язык, состоящий из всех цепочек, в которых п единиц следуют за п нулями для некоторого п > 0:{е, 01,0011,000111, …}.
2. Множество цепочек, состоящих из 0 и 1 и содержащих поровну тех и других: {е, 01, 10, ООП, 1001, …}.
3. Множество двоичных записей простых чисел: {10, 11, 101, 111,1011, …}.
4. — язык для любого алфавита Е.
5. 0 — пустой язык в любом алфавите.
6. {£■} — язык, содержащий одну лишь пустую цепочку. Он также является языком в любом алфавите. Заметим, что 0 * {е}; первый не содержит вообще никаких цепочек, а второй состоит из одной цепочки.
Единственное существенное ограничение для множеств, которые могут быть языками, состоит в том, что все алфавиты конечны. Таким образом, хотя языки и могут содержать бесконечное число цепочек, но эти цепочки должны быть составлены из символов некоторого фиксированного конечного алфавита.

1.5.4. Проблемы
В теории автоматов проблема — это вопрос о том, является ли данная цепочка элементом определенного языка. Как мы вскоре выясним, все, что называется «проблемой» в более широком смысле слова, может быть выражено в виде проблемы принадлежности некоторому языку. Точнее, если £ — некоторый алфавит, и L — язык в то проблема L формулируется следующим образом.
• Дана цепочка w из X*, требуется выяснить, принадлежит цепочка w языку L, или нет.
Пример 1.26. Задачу проверки простоты данного числа можно выразить в терминах принадлежности языку Lp, который состоит из всех двоичных цепочек, выражающих простые числа. Таким образом, ответ «да» соответствует ситуации, когда данная цепочка из нулей и единиц является двоичным представлением простого числа. В противном случае ответом будет «нет». Для некоторых цепочек принять решение довольно просто. Например, цепочка 0011101 не может быть представлением простого числа по той причине, что двоичное представление всякого целого числа, за исключением 0, начинается с 1. Однако решение данной проблемы для цепочки 11101 не так очевидно и требует значительных затрат таких вычислительных ресурсов, как время и/или объем памяти. □
Описание множеств как способ определения языков
Языки часто задаются с помощью конструкции, описывающей множество: {w | сведения о w}.
Читается данное выражение так: «множество слов w, соответствующих тому, что сказано о w справа от вертикальной черты». Например:
1. {w | w содержит поровну нулей и единиц}.
2. {w | w есть двоичное представление простого числа}.
3. {w | w есть синтаксически правильная программа на языке С}.
Кроме того, часто вместо w пишут некоторое выражение, зависящее от параметров, и описывают цепочки языка, накладывая на эти параметры определенные условия. В первом из следующих примеров в качестве параметра фигурирует п, а во втором — параметры / и j.
1. {0″l» | п> 1}. Читается: «множество цепочек из п нулей и п единиц, где п больше или равно 1». Этот язык содержит цепочки {01,0011, 000111,…}. Заметим, что, как и для алфавита, мы можем определить и-ю степень одиночного символа как цепочку из п копий данного символа.
2. {О’ \J | 0 < / <j). Этот язык состоит из цепочек, у которых вначале идет некоторое (возможно, нулевое) число нулей, а затем некоторое число единиц, причем число последних не меньше числа нулей.
В приведенном нами определении «проблемы» есть одно слабое место. Дело в том, что обычно под проблемами подразумевают не вопросы разрешения (истинно нечто, или нет), а запросы на обработку или преобразование некоторых входных данных (желательно, наилучшим способом). Например, задача анализатора в компиляторе языка С — определить, принадлежит ли данная цепочка символов ASCII множеству Lc всех правильных программ на С — в точности соответствует нашему определению. Но в задачи анализатора входят также формирование дерева синтаксического анализа, заполнение таблицы имен и, возможно, другие действия. Хуже того, компилятор в целом решает задачу перевода С-программы в объектный код для некоторой машины, и эта задача весьма далека от простого ответа «да» или «нет» на вопрос о правильности такой программы.
Тем не менее, определение «проблем» как языков выдержало проверку временем и позволяет нам успешно решать многие задачи, возникающие в теории сложности. В рамках этой теории мы отыскиваем нижние границы сложности определенных задач. Особенно важны тут методы доказательства того, что определенные типы задач не могут быть решены за время, меньшее по количеству, чем экспонента от размера их входных данных. Оказывается, что в этом смысле задача, сформулированная в терминах теории языков (т.е. требующая ответа «да» или «нет»), так же трудна, как и исходная задача, требующая «найти решение».
Таким образом, если мы можем доказать, что трудно определить, принадлежит ли данная цепочка множеству /,х всех правильных программ на языке X, следовательно, переводить программы с языка Л’в объектный код, по крайней мере, не легче. В самом деле, если было бы легко генерировать код, то мы могли бы попросту запустить транслятор и, когда он успешно выработал бы объектный код, заключить, что входная цепочка является правильной программой, принадлежащей Lx■ Поскольку последний шаг определения, выработан ли объектный код, не может быть сложным, то с помощью быстрого алгоритма генерации кода мы могли бы эффективно решать задачу о принадлежности цепочки множеству Lx. Но так мы приходим к противоречию с предположением о том, что определить принадлежность цепочки языку /,х трудно. Итак, мы доказали методом от противного утверждение «если проверка принадлежности языку /,х трудна, то и компиляция программ, написанных на языке X, также трудна».
Этот метод, позволяющий показать трудность одной задачи с использованием предполагаемого эффективного алгоритма ее решения для эффективного решения другой, заведомо сложной задачи, называется «сведением» второй задачи к первой. Это мощный инструмент в исследованиях сложности проблем, причем его применение значительно упрощается в силу нашего замечания о том, что проблемами, по сути, являются лишь вопросы о принадлежности некоторому языку.
Что это — язык или проблема?
На самом деле, язык и проблема — это одно и то же. Употребление терминов зависит лишь от нашей точки зрения. Когда нас интересуют цепочки сами по себе, например, множество {0″1″| л> 1}, мы склонны видеть в этом множестве цепочек некоторый язык. В последних главах этой книги мы будем больше интересоваться «семантикой» цепочек, т.е. рассматривать цепочки как закодированные графы, логические выражения или целые числа. В этих случаях нас будут больше интересовать не сами цепочки, а те объекты, которые они представляют. И тогда мы будем склонны рассматривать множество цепочек как некую проблему.
Резюме
♦ Конечные автоматы. Конечные автоматы включают набор состояний и переходов между ними, зависящих от входных данных. Они весьма полезны при построении различных систем программного обеспечения, включая лексические анализаторы компиляторов и системы проверки корректности схем или протоколов.
♦ Регулярные выражения. Это структурные записи для описания некоторых шаблонов, представимых конечными автоматами. Используются во многих компонентах программного обеспечения, например, в программах поиска по шаблону в текстах или среди файловых имен.
♦ Контекстно-свободные грамматики. Эта важная система описания структуры языков программирования и связанных с ними множеств цепочек используется при построении такого компонента компилятора, как анализатор.
♦ Машины Тьюринга. Автоматы, моделирующие все возможности реальных вычислительных машин. Позволяют изучать разрешимость, т.е. вопрос о том, что можно и чего нельзя сделать с помощью компьютера. Кроме того, они позволяют отличать задачи, разрешимые за полиномиальное время, от неразрешимых.
♦ Дедуктивные доказательства. Основной метод доказательства, состоящий из цепочки утверждений, которые либо даны как истинные, либо логически следуют из предыдущих утверждений.
♦ Доказательства утверждений типа «если-то». Многие теоремы имеют вид: «если (нечто одно), то (нечто другое)». Утверждение (или утверждения), стоящее в скобках после «если», является гипотезой, а утверждение, стоящее после слова «то», — заключением. Цепочка дедуктивных доказательств утверждений этого типа начинается с гипотезы, из которой последовательно логически выводятся новые утверждения до тех пор, пока на каком-то шаге одно из них не совпадет с заключением.
♦ Доказательства утверждений типа «тогда и только тогда». Существуют теоремы вида «(нечто одно) тогда и только тогда, когда (нечто другое)». Доказываются такие утверждения в одну и другую стороны как утверждения типа «если-то». Этот вид теорем очень близок к утверждениям о равенстве двух множеств, записанных разными способами. Для их доказательства нужно показать, что каждое из этих множеств содержится в другом.
♦ Доказательство контрапозиции. Доказать утверждение типа «если Я, то С» иногда бывает легче путем доказательства эквивалентного утверждения «если не С, то не Я’, которое называют контрапозицией исходного.
♦ Доказательство методом «от противного». В некоторых случаях удобнее вместо утверждения «если Я, то С» доказывать утверждение «если Я и не С, то (нечто заведомо ложное)». Этот метод доказательства называется доказательством от противного.
♦ Контрпримеры. Иногда необходимо доказывать, что некоторое утверждение не является истинным. Если это утверждение содержит один или несколько параметров, то можно доказать его ложность в целом, приведя всего один контрпример, т.е. подобрав такие значения параметров, при которых это утверждение ложно.
♦ Индуктивные доказательства. Утверждения, содержащие целый параметр п, очень часто могут быть доказаны по индукции. Для этого мы доказываем, что данное утверждение истинно для базиса, конечного числа случаев определенных значений п. Затем доказываем, что если утверждение истинно для п, то оно истинно и для п + 1.
♦ Структурная индукция. Довольно часто в этой книге возникает ситуация, когда в теореме, требующей индуктивного доказательства, речь идет о таких рекурсивно определяемых понятиях, как деревья. Тогда теорему о построенных таким способом объектах можно доказывать индукцией по числу шагов, использованных при их построении. Этот тип индукции называют структурной индукцией.
♦ Алфавиты. Алфавитом является некоторое конечное множество символов.
♦ Цепочки. Цепочкой называют конечную последовательность символов.
♦ Языки и проблемы. Язык есть (вообще говоря, бесконечное) множество цепочек, состоящих из символов некоторого фиксированного алфавита. Если цепочки языка должны быть проинтерпретированы некоторым способом, вопрос о принадлежности определенной цепочки этому языку иногда называют проблемой.
Литература
Для углубленного изучения материала этой главы, посвященной основополагающим математическим понятиям информатики, мы рекомендуем книгу [1].
1. А. V. Aho and J. D. Ullman, Foundations of Computer Science, Computer Science Press, New York, 1994.