dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 10

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

Аналогично G содержит n + 1 правых скобок (одна явная и n в E).Итак, в каждом из этих трех случаев число правых и левых скобок в G одинаково, аэто значит, что теорема доказана. †1.4.4. Ñîâìåñòíàÿ èíäóêöèÿИногда мы не можем доказать по индукции некоторое отдельно взятое утверждение,и вместо этого нам нужно доказать совместно целую группу утверждений S1(n), S2(n), …,Sk(n) с помощью индукции по n.

В теории автоматов такая ситуация встречается довольно часто. Так, в примере 1.23 мы рассмотрим общую ситуацию, в которой действие автомата описывается группой утверждений, по одному для каждого из состояний. В этихутверждениях говорится, какие последовательности входных сигналов приводят автоматв каждое из его состояний.Строго говоря, доказательство группы утверждений не отличается от доказательстваконъюнкции (логическое “И”) всех этих утверждений. Например, группу утвержденийS1(n), S2(n), ..., Sk(n) можно заменить одним утверждением S1(n) И S2(n) И … И Sk(n). Однако, если необходимо доказывать несколько действительно независимых утверждений,то проще рассматривать их отдельно и для каждого из них доказывать свой базис и индуктивный шаг.

Этот тип доказательства назовем совместной индукцией. В следующемпримере мы покажем, какие основные этапы должно содержать такое доказательство.Пример 1.23. Вернемся к примеру 1.1, где в виде автомата был представлен переключатель состояний “вкл.-выкл.”. Сам автомат еще раз воспроизведен на рис. 1.8. Нажатие кнопки переводит автомат из одного состояния в другое, а в качестве начального выбрано состояние “выкл.”, поэтому можно предполагать, что поведение переключателяописывается системой из следующих двух утверждений.S1(n): после n нажатий кнопки автомат находится в состоянии “выкл.” тогда и толькотогда, когда n — четное число.S2(n): после n нажатий кнопки автомат находится в состоянии “вкл.” тогда и толькотогда, когда n — нечетное число.1.4. ÈÍÄÓÊÒÈÂÍÛÅ ÄÎÊÀÇÀÒÅËÜÑÒÂÀСтр.

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

В качестве базисного значения выберем n = 0. Поскольку требуется доказатьдва утверждения типа “тогда и только тогда”, причем каждое из них в обе стороны, тофактически нужно рассмотреть четыре базисных случая и четыре шага индукции.1.[S1; достаточность] Поскольку 0 — четное число, мы должны показать, что после 0нажатий автомат на рис. 1.8 находится в состоянии “выкл.”. Но это действительнотак, поскольку начальное состояние автомата — “выкл.”.2.[S1; необходимость] После 0 нажатий автомат находится в состоянии “выкл.”, поэтому нам нужно показать, что 0 — четное число. Но тут и доказывать нечего, поскольку 0 есть четное число по определению.3.[S2; достаточность] Гипотеза достаточности S2 состоит в том, что 0 — нечетноечисло. Очевидно, она ложна. А поскольку гипотеза H ложна, то, как показано в разделе 1.3.2, всякое утверждение вида “если H, то C” истинно.

Таким образом, и этачасть базиса верна.4.[S2; необходимость] Гипотеза о том, что после 0 нажатий автомат находится в состоянии “вкл.” также ложна, так как в это состояние мы попадаем только по стрелке“Нажатие”, а это означает, что на кнопку нажали хотя бы один раз. Отсюда, как иранее, приходим к выводу, что утверждение типа “если-то” истинно, поскольку егогипотеза ложна.Индукция. Предположим теперь, что S 1(n) и S 2(n) истинны, и докажем утверждения S 1(n + 1) и S 2(n + 1). Это доказательство также разделяется на следующиечетыре части.44Стр. 44ÃËÀÂÀ 1. ÀÂÒÎÌÀÒÛ: ÌÅÒÎÄÛ È ÏÎÍßÒÈß1.[S1(n + 1); достаточность] Гипотезой для этой части является то, что n + 1 —четное число, т.е. n — нечетное.

В этом случае из достаточности утвержденияS2(n) следует, что после n нажатий автомат находится в состоянии “вкл.”. Дуга из“вкл.” в “выкл.”, обозначенная сигналом “Нажатие”, указывает, что (n + 1)-е нажатие переводит автомат в состояние “выкл.”. Таким образом, доказана достаточность утверждения S1.2.[S1(n + 1); необходимость] Предположим, что после (n + 1)-го нажатия автомат находится в состоянии “выкл.”. Тогда, анализируя автомат на рис.

1.8, можно сделатьвывод, что в состояние “выкл.” мы попадаем, находясь в состоянии “вкл.” и получаяна вход “Нажатие”. Таким образом, если после (n + 1)-го нажатия мы находимся всостоянии “выкл.”, то после n нажатий мы находились в состоянии “вкл.”. Но тогдаиз необходимости утверждения S2(n) заключаем, что n — нечетное число. Следовательно, n + 1 — число четное, а это и есть нужное нам заключение “необходимости”в утверждении S1(n + 1).3.[S2(n + 1); достаточность] Для доказательства этой части достаточно в пункте (1)поменять местами утверждения S2 и S1, а также слова “четное” и “нечетное”. Не сомневаемся, что читатель самостоятельно восстановит это доказательство.4.[S2(n + 1); необходимость] Для этого доказательства достаточно в п.

2 поменятьместами S2 и S1, а также “нечетное” и “четное”.†На основе примера 1.23 можно сделать следующие общие выводы относительно совместных индуктивных доказательств.• Для каждого утверждения нужно отдельно доказать и базис, и индуктивный шаг.• Если утверждения имеют вид “тогда и только тогда”, то при доказательстве и базиса, и шага индукции утверждения нужно доказывать в обе стороны.1.5. Îñíîâíûå ïîíÿòèÿ òåîðèè àâòîìàòîâВ этом разделе вводятся наиболее важные из понятий, которыми оперирует теорияавтоматов: “алфавит” (множество символов), “цепочка” (последовательность символовнекоторого алфавита) и “язык” (множество цепочек в одном и том же алфавите).1.5.1. ÀëôàâèòûАлфавитом называют конечное непустое множество символов.

Условимся обозначать алфавиты символом Σ. Наиболее часто используются следующие алфавиты.1.Σ = {0,1} — бинарный или двоичный алфавит.2.Σ = {a, b, …, z} — множество строчных букв английского алфавита.1.5. ÎÑÍÎÂÍÛÅ ÏÎÍßÒÈß ÒÅÎÐÈÈ ÀÂÒÎÌÀÒÎÂСтр. 45453.Множество ASCII-символов или множество всех печатных ASCII-символов.1.5.2. Öåïî÷êèЦепочка, или иногда слово, — это конечная последовательность символов некоторогоалфавита. Например, 01101 — это цепочка в бинарном алфавите Σ = {0, 1}.

Цепочка 111также является цепочкой в этом алфавите.Ïóñòàÿ öåïî÷êàПустая цепочка — это цепочка, не содержащая ни одного символа. Эту цепочку,обозначаемую ε, можно рассматривать как цепочку в любом алфавите.Äëèíà öåïî÷êèЧасто оказывается удобным классифицировать цепочки по их длине, т.е. по числу позиций для символов в цепочке. Например, цепочка 01101 имеет длину 5. Обычно говорят, что длина цепочки — это “число символов” в ней. Это определение широко распространено, но не вполне корректно. Так, в цепочке 01101 всего 2 символа, но число позиций в ней — пять, поэтому она имеет длину 5.

Все же следует иметь в виду, что частопишут “число символов”, имея в виду “число позиций”.Длину некоторой цепочки w обычно обозначают |w|. Например, |011| = 3, а |ε| = 0.Ñòåïåíè àëôàâèòàЕсли Σ — некоторый алфавит, то можно выразить множество всех цепочек определенной длины, состоящих из символов данного алфавита, используя знак степени.

Определим Σk как множество всех цепочек длины k, состоящих из символов алфавита Σ.Пример 1.24. Заметим, что Σ0 = {ε} независимо от алфавита Σ, т.е. ε — единственнаяцепочка длины 0.Если Σ = {0, 1}, то Σ1 = {0, 1}, Σ2 = {00, 01, 10, 11}, Σ3 = {000, 001, 010, 011, 100, 101,110, 111} и так далее. Отметим, что между Σ и Σ1 есть небольшое различие. Дело втом, что Σ есть алфавит, и его элементы 0 и 1 являются символами, а Σ1 является множеством цепочек, и его элементы — это цепочки 0 и 1, каждая длиной 1.

Мы не будемвводить разные обозначения для этих множеств, полагая, что из контекста будет понятно, является {0, 1} или подобное ему множество алфавитом или же множествомцепочек. †Ñîãëàøåíèÿ î ñèìâîëàõ è öåïî÷êàõКак правило, строчными буквами из начальной части алфавита (или цифрами) мы будем обозначать символы, а строчными буквами из конца алфавита, например w, x, yили z — цепочки. Руководствуясь этим соглашением, вы легко сможете понять, элементы какого типа рассматриваются в том или ином случае.46Стр. 46ÃËÀÂÀ 1. ÀÂÒÎÌÀÒÛ: ÌÅÒÎÄÛ È ÏÎÍßÒÈßМножество всех цепочек над алфавитом Σ принято обозначать Σ*.

Так, например,{0,1}* = {ε, 0, 1, 00, 01, 10, 11, 000, …}. По-другому это множество можно записать в виде*012Σ =Σ UΣ UΣ U…Иногда нам будет необходимо исключать из множества цепочек пустую цепочку.Множество всех непустых цепочек в алфавите Σ обозначают через Σ+. Таким образом,имеют место следующие равенства:• Σ+ = Σ1 U Σ2 U Σ3 U …• Σ * = Σ + U {ε }.Êîíêàíòåíàöèÿ öåïî÷åêПусть x и y — цепочки. Тогда xy обозначает их конкатенацию (соединение), т.е. цепочку, в которой последовательно записаны цепочки x и y. Более строго, если x — цепочка из i символов: x = a1a2…ai, а y — цепочка из j символов: y = b1b2…bj, то xy — этоцепочка длины i + j: xy = a1a2…aib1b2…bj.Пример 1.25.

Пусть x = 01101 и y = 110. Тогда xy = 01101110, а yx = 11001101. Длялюбой цепочки w справедливы равенства εw = wε = w. Таким образом, ε является единицей (нейтральным элементом) относительно операции конкантенации, поскольку результат ее конкатенации с любой цепочкой дает ту же самую цепочку (аналогично томукак 0, нейтральный элемент относительно сложения, при сложении с любым числом xдает число x). †1.5.3. ßçûêèМножество цепочек, каждая из которых принадлежит Σ*, где Σ — некоторый фиксированный алфавит, называют языком2.

Если Σ — алфавит, и L ⊆ Σ*, то L — это язык надΣ, или в Σ. Отметим, что язык в Σ не обязательно должен содержать цепочки, в которыевходят все символы Σ. Поэтому, если известно, что L является языком в Σ, то можно утверждать, что L — это язык над любым алфавитом, содержащим Σ.Термин “язык” может показаться странным. Однако оправданием служит то, что иобычные языки можно рассматривать как множества цепочек. Возьмем в качестве примера английский язык, где набор всех литературных английских слов есть множествоцепочек в алфавите (английских же букв).

Характеристики

Список файлов книги