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

Однако следует помнить, что, как и в разделе 1.4.1, данное апеллирующее к интуиции пояснение не является формальным доказательством. Фактически, мы должны допустить справедливость этого принципа, так же, как в том разделе допустили справедливость исходного принципа индукции. 1.4. ИНДУКТИВНЫЕ ДОКАЗАТЕЛЬСТВА Если у нас имеется рекурсивное определение некоторого понятия, то теоремы относительно этого понятия можно доказывать с помошью следующего метода, называемого структурной индукцией. Пусть о(Х) — утверждение о структурах Х, опреде- ляемых рекурсивно. 1.

В качестве базиса докажем утверждение ЗЩ для базисной структуры (или струкур) Х. 2. Для индуктивного перехода возьмем структуру Х, определенную рекурсивно через Уь Уь ..., Уь Предполагая, что верны утверждения Я(У~), З(У~), ..., о(уз), докажем с их помощью 5(Х). Отсюда заключаем, что ЯГХ) истинно для всех Х. В следующих двух примерах мы доказываем теоремы о деревьях и выражениях.

Теорема 1.21. В любом дереве число узлов на единицу больше числа ребер. Доказательство. Запишем утверждение о(Т), которое нам требуется доказать методом структурной индукции в формальном виде: "Если Т вЂ” дерево, и Т содержит и узлов и е ребер, то и = е+ !". Базис. В качестве базисного выберем случай, когда дерево Т состоит из одного узла. Тогда н =! и е = О, а потому соотношение и = е+ 1 выполнено. Индукции. Пусть Т вЂ” дерево, построенное по индуктивному определению из корневого узла !т' и к меньших деревьев Ть Ть ..., Ть Предположим, что утверждение $(Т) истинно при ! = 1, 2, ..., х, т.е., если дерево Т; содержит и, узлов и е, ребер, то и; = е, + 1. Узлы дерева Т вЂ” это узел 1т' и все узлы деревьев Т,.

Таким образом, Т содержит 1 + из + из + ... + щ узлов. Ребра Т вЂ” это й ребер, которые мы добавили на индуктивном шаге определения, плюс все ребра деревьев Т,. Значит, Т содержит (!.10) /с + е, + ез + ... + ез ребер. Заменив и; на е, + 1 в выражении для числа узлов Т, получим, что оно равно 1 + [е~ + 1] + [ег + 11+ ...

+ [е, + 1!. (1 И) Поскольку в сумме (1.11) содержится х слагаемых вида "+1", ее можно перегруппировать таким образом. к + ! + ез + ег .!-, . ь ез (1.12) Это выражение равно на единицу больше, чем значение выражения (!.10), показывающего число ребер Т. Таким образом, число узлов на единицу больше числа ребер, ЕЗ Теорема 1.22. Всякое выражение содержит поровну правых и левых скобок. Доказательство. Говоря формально, необходимо доказать такое утверждение З(О) относительно выражения с, определенного рекурсивно в примере 1.20: левых н правых скобок в О поровну. Базис. Если б — базисное выражение, то это либо число, либо переменная.

В этих выражениях 0 левых и 0 правых скобок, т.е. поровну, ГЛАВА 1. АВТОМАТЫ: МЕТОДЫ И ПОНЯТИЯ 42 Индукция. По определению индуктивного шага существует три способа построения выражения О. 1. б=Е+Г 2. С=Е'Г 3. б = (Е). Мы предполагаем, что утверждения Я(Е) и 5(Г) истинны, т.е. что каждое из выражений Е н Е содержит поровну правых и левых скобок, по и и т, соответственно. Тогда в каждом из трех случаев мы можем подсчитать число входящих в б правых и левых скобок.

1. Если О = Е+ Е, то О содержит по и+ е скобок каждого сорта: по и левых н правых скобок из выражения Е, и по гл — из Е 2. Если б = Е ь Р, то О также содержит по и+ т скобок каждого сорта, как и в случае (1). 3. Если же б = (Е), то б содержит л е 1 левых скобок — одну мы видим явно, а л находятся в Е. Аналогично 0 содержит и + 1 правых скобок (одна явная и и в Е). Итак, в каждом из этих трех случаев число правых и левых скобок в б одинаково, а это значит, что теорема доказана.

П 1.4.4. Совместная индукция Иногда мы не можем доказать по индукции некоторое отдельно взятое утверждение, и вместо этого нам нужно доказать совместно целую группу утверждений Я~(л), Я,(и), ..., Яз(л) с помощью индукции по я. В теории автоматов такая ситуация встречается довольно часто. Так, в примере 1.23 мы рассмотрим общую ситуацию, в которой действие автомата описывается группой утверждений, по одному для каждого из состояний. В этих утверждениях говорится, какие последовательности входных сигналов приводят автомат в каждое из его состояний. Строго говоря, доказательство группы утверждений не отличается от доказательства коньюнкции (логическое "И") всех этих утверждений. Например, группу утверждений 51(п), 5,(л), ., Яц(л) можно заменить одним утверждением 5,(л) И Яз(и) И ... И 5„(л). Однако, если необходимо доказывать несколько действительно независимых утверждений, то проще рассматривать их отдельно и для каждого из них доказывать свой базис и индуктивный шаг.

Этот тип доказательства назовем совместной индукцией. В следующем примере мы покажем, какие основные этапы должно содержать такое доказательство. Пример 1.23. Вернемся к примеру 1.1, где в виде автомата был представлен переключатель состояний чвкл.-выкл,", Сам автомат еще раз воспроизведен на рис.

1.8. Нажатие кнопки переводит автомат из одного состояния в другое, а в качестве начального выбрано состояние "выкя.", поэтому можно предполагать, что поведение переключателя описывается системой из следующих двух утверждений. 1.4. ИНДУКТИВНЫЕ ДОКАЗАТЕЛЬСТВА 43 Я,(п): после п нажатий кнопки автомат находится в состоянии "выкл." тогда и только тогда, когда и — четное число. Я2(п): после и нажатий кнопки автомат находится в состоянии "вкл." тогда и только тогда, когда п — нечетное число. Нажатие Неч Нажатие Рис.

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

Базис. В качестве базисного значения выберем п = О. Поскольку требуется доказать два утверждения типа "тогда и только тогда", причем каждое из них в обе стороны, то фактически нужно рассмотреть четыре базисных случая и четыре шага индукции. 1. (Вб достаточность'1 Поскольку Π— четное число, мы должны показать, что после О нажатий автомат на рис. 1.8 находится в состоянии "выкл.". Но это действительно так, поскольку начальное состояние автомата — "выкл.".

2. (Яб необходимость'! После О нажатий автомат находится в состоянии "выкл.", поэтому нам нужно показать, что Π— четное число. Но тут и доказывать нечего, поскольку О есть четное число по определению. 3. (Яг., достагпогаюсть] Гипотеза достаточности Вз состоит в том, что Π— нечетное число. Очевидно, она ложна. А поскольку гипотеза О ложна, то„как показано в разделе 1.3.2, всякое утверждение вида "если Н, то С' истинно. Таким образом, и эта часть базиса верна.

4. (Я; необходимость) Гипотеза о том, что после О нажатий автомат находится в со- стоянии "вкл." также ложна, так как в это состояние мы попадаем только по стрелке "Нажатие'", а это означает, что на кнопку нажали хотя бы один раз. Отсюда, как и ГЛАВА 1. АВТОМАТЫ: МЕТОДЫ И ПОНЯТНЯ ранее, прихолим к выводу, что утверждение типа "если-то" истинно, поскольку его гипотеза ложна. Индукции. Предположим теперь, что Я,(п) и Яз(п) истинны, и докажем утверждения 5,(п.ь 1) и Я,(п+ 1). Это доказательство также разделяется на следующие четыре части.

1. [Я,(и+1); достаточность) Гипотезой для этой части является то, что и+ !в четное число, т.е. и — нечетное. В этом случае из достаточности утверждения Я,(п) следует, что после и нажатий автомат находится в состоянии "вкл.". Дуга из "вял." в "выкл.", обозначенная сигналом "Нажатие", указывает, что (и ч 1)-е нажатие переводит автомат в состояние "выкл.". Таким образом, доказана достаточность утверждения Яь 2. [Я~(п + 1); иеобходаиость] Предположим, что после (и+!)-го нажатия автомат находится в состоянии "выкл.", Тогда, анализируя автомат на рис.

1.8, можно сделать вывод, что в состояние "выкл." мы попадаем, находясь в состоянии "акл." и получая на вход "Нажатие". Таким образом, если после (и+ 1)-го нажатия мы находимся в состоянии "выкл.", то после и нажатий мы находились в состоянии "вкл.", Но тогда из необходимости утверждения Б~(и) заключаем, что п — нечетное число. Следовательно,п + ! — число четное, а это и есть нужное нам заключение "необходимости*' в утверждении 5~(п ч 1). 3, [о2(п+ 1); достаеочиость) Для доказательства этой части достаточно в пункте (!) поменять местами утверждения 5~ и Яь а также слова "четное" и "нечетное".

Не сомневаемся, что читатель самостоятельно восстановит это доказательство. 4. [Яз(и+1); необходимость) Для этого доказательства достаточно в п.2 поменять местами Яз и бл а также "нечетное" и "четное". На основе примера 1.23 можно сделать следующие общие выводы относительно совместных индуктивных доказательств. ° Для каждого утверждения нужно отдельно доказать и базис, и индуктивный шаг. ° Если утверждения имеют вид "тогда и только тогда", то при доказательстве и базиса, и шага индукции утверждения нужно доказывать в обе стороны. 1.5. Основные понятия теории автоматов В этом разделе вводятся наиболее важные из понятий, которыми оперирует теория автоматов: "алфавит" (множество символов), "цепочка" (последовательность символов некоторого алфавита) и "язык" (множество цепочек в одном и том же алфавите). 1.б.