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

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

Итак, мы доказали методом от противного утверждение "если проверка принадлежности языку Ех трудна, то и компиляция программ, написанных на языке Х также трудна". Этот метод, позволяющий показать трудность одной задачи с использованием предполагаемого эффективного алгоритма ее решения для эффективного решения другой, заведомо сложной задачи, называется "сведением" второй задачи к первой. Это мощный инструмент в исследованиях сложности проблем, причем его применение значительно упрощается в силу нашего замечания о том, что проблемами, по сути, являются лишь во- просы о принадлежности некоторому языку.

Что зто — язык или проблема' ? На самом деле, язык и проблема — это одно и то же. Употребление терминов зависит лишь от нашей точки зрения. Когда нас интересуют цепочки сами по себе, например, множество !О"1" ! и >! 1, мы склонны видеть в этом множестве цепочек некоторый язык. В последних главах этой книги мы будем больше интересоваться "семантикой" цепочек, т.е.

рассматривать цепочки как закодированные графы, логические выражения или целые числа. В этих случаях нас будут больше интересовать не сами цепочки, а те объекты, которые они представляют. И тогда мы будем склонны рассматривать множество цепочек как некую проблему. Резюме + Конечные автомаглы. Конечные автоматы включают набор состояний и переходов между ними, зависящих от входных данных. Они весьма полезны при построении различных систем программного обеспечения, включая лексиче- ГЛАВА 1. АВТОМАТЫ: МЕТОДЫ И ПОНЯТИЯ 50 ские анализаторы компиляторов и системы проверки корректности схем или протоколов. в Регулярные выражения.

Это структурные записи для описания некоторых шаблонов, представимых конечными автоматами. Используются во многих компонентах программного обеспечения, например, в программах поиска по шаблону в текстах или среди файловых имен. в Контекстно-свободные грамматики. Эта важная система описания структуры языков программирования и связанных с ними множеств цепочек используется при построении такого компонента компилятора, как анализатор.

в Машины Тьюринга. Автоматы, моделируюшие все возможности реальных вычислительных машин. Позволяют изучать разрешимость, т.е. вопрос о том, что можно и чего нельзя сделать с помощью компьютера. Кроме того, они позволяют отли- чать задачи, разрешимые за полиномиальное время, от неразрешимых. в Дедуктивные даказатезьства. Основной метод доказательства, состояший из цепочки утверждений, которые либо даны как истинные, либо логически следуют из предыдуших утверждений. в Доказательства утверждений типа "если-та". Многие теоремы имеют вид: "если (нечто одно)„то (нечто другое)". Утверждение (или утверждения), стоящее в скобках после "если*', является гипотезой, а утверждение, стоящее после слова "то", — заключением.

Цепочка дедуктивных доказательств утверждений этого типа начинается с гипотезы, из которой последовательно логически выводятся но- вые утверждения до тех пор, пока на каком-то шаге одно из них не совпадет с за- ключением. в Доказательства утверждений типа "тогда и только тогда". Сушествуют теоремы вида "(нечто одно) тогда и только тогда, когда (нечто другое)'*. Доказываются такие утверждения в одну и другую стороны как утверждения типа "если-то". Этот вид теорем очень близок к утверждениям о равенстве двух множеств, записанных разными способами, Для их доказательства нужно показать, что каждое из этих множеств содержится в другом.

в Доказательство кантрапазилии. Доказать утверждение типа "если Н, то С' иногда бывает легче путем доказательства эквивалентного утверждения "если не С, то не Н", которое называют контрапозицией исходного. в Доказательства методом "ат противного". В некоторых случаях удобнее вместо утверждения "если Н, то С"' доказывать утверждение "если Н и не С, то (нечто заведомо ложное)". Этот метод доказательства называется доказательством от противного. РЕЗЮМЕ е Кантрпричерьь Иногда необходимо доказывать, что некоторое утверждение не является истинным.

Если это утверждение содержит один или несколько парамет- ров, то можно доказать его ложность в целом, приведя всего один контрпример, т.е. подобрав такие значения параметров, при которых это утверждение ложно. + Индуктивные доказательства. Утверждения, содержащие целый параметр и, очень часто могут быть доказаны по индукции. Для этого мы доказываем, что данное утверждение истинно для базиса, конечного числа случаев определенных значений и.

Затем доказываем, что если утверждение истинно для и, то оно истинно и для и + 1 + Структурная индуклия. Довольно часто в этой книге возникает ситуация, когда в теореме, требующей индуктивного доказательства, речь идет о таких рекурсивно определяемых понятиях, как деревья. Тогда теорему о построенных таким способом объектах можно доказывать индукцней по числу щагов, использованных при их построении.

Этот тип индукции называют структурной индукцией. Алфавиты. Алфавитом является некоторое конечное множество символов. + Цепочки. Цепочкой называют конечную последовательность символов. Языки и проблемы. Язык есть (вообще говоря, бесконечное) множество цепочек, состоящих из символов некоторого фиксированного алфавита. Если цепочки языка должны быть проинтерпретированы некоторым способом, вопрос о принадлежности определенной цепочки этому языку иногда называют проблемой. Литература Для углубленного изучения материала этой главы, посвященной основополагающим математическим понятиям информатики, мы рекомендуем книгу [1]. 1. А. у, Айо апд 3. П.

ППщап, гоипг1агГапл аГ Сатригег БсГепсв, Сощрщег Бс!епсе Ргеяз, гче и Уог1с, 1994. ГЛАВА 1. АВТОМАТЫ: МЕТОДЫ И ПОНЯТИЯ 52 ГЛАВА 2 Конечные автоматы В этой главе мы введем класс языков, известных как "регулярные". Это языки, которые могут быль описаны конечными автоматами.

Последние мы уже обсудили вкратце в разделе!.! .1. Перед тем как формально определить конечные автоматы, рассмотрим развернутый пример, из которого станет ясной мотивация последующего изучения этих объектов. Как указывалось ранее, конечный автомат состоит из множества состояний и ''управления", переводящего из одного состояния в другое в зависимости от получаемых извне "входных данных". Классы автоматов существенно различаются по типу этого управления. Управление может быть "детерминированным*' в том смысле, что автомат может находиться в каждый момент времени не более чем в одном состоянии, и "недетерминированным", т.е. автомат может одновременно находиться в нескольких состояниях.

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

В заключительной части главы изучается расширенный недетерминированный автомат, который имеет дополнительную возможность переходить из состояния в состояние спонтанно, т.е. по пустой цепочке в качестве входа. Эти автоматы также описывают только регулярные языки. Тем не менее, они окажутся совершенно необходимыми в главе 3 при изучении регулярных выражений и доказательстве их эквивалентности автоматам.

Изучение регулярных языков продолжается в главе 3. Там представлен еще один важный способ их описания посредством такой алгебраической нотации, как регулярное выражение. Мы изучим регулярные выражения и покажем их эквивалентность конечным автоматам, чтобы в главе 4 использовать и те, и другие как инструменты для доказательства некоторых важных свойств регулярных языков.

Например, свойства 'замкнутости", позволяющие утверждать, что некоторый язык является регулярным, на том основании, что один или несколько других языков регулярны. Еще один пример — "разрешимые" свойства, т.е, наличие алгоритмов, позволяющих ответить на вопросы, касающиеся ав- томата или регулярного выражения, например, представляют ли два различных автомата илн регулярных выражения один и тот же язык.

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

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