dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 11
Текст из файла (страница 11)
Еще один пример — язык программированияC или любой другой язык программирования, в котором правильно написанные программы представляют собой подмножество множества всех возможных цепочек, а цепочки состоят из символов алфавита данного языка. Этот алфавит является подмножеством символов ASCII. Алфавиты для разных языков программирования могут быть раз-2В таком определении язык часто называется формальным. — Прим. ред.1.5. ÎÑÍÎÂÍÛÅ ÏÎÍßÒÈß ÒÅÎÐÈÈ ÀÂÒÎÌÀÒÎÂСтр. 4747личными, хотя обычно они состоят из прописных и строчных букв, цифр, знаков пунктуации и математических символов.Существует, однако, множество других языков, изучаемых в теории автоматов.
Приведем несколько примеров.1.Язык, состоящий из всех цепочек, в которых n единиц следуют за n нулями для некоторого n ≥ 0:{ε, 01, 0011, 000111, …}.2.Множество цепочек, состоящих из 0 и 1 и содержащих поровну тех и других: {ε, 01,10, 0011, 1001, …}.3.Множество двоичных записей простых чисел: {10, 11, 101, 111,1011, …}.4.Σ* — язык для любого алфавита Σ.5.∅ — пустой язык в любом алфавите.6.{ε} — язык, содержащий одну лишь пустую цепочку.
Он также является языком влюбом алфавите. Заметим, что ∅ ≠ {ε}; первый не содержит вообще никаких цепочек, а второй состоит из одной цепочки.Единственное существенное ограничение для множеств, которые могут быть языками, состоит в том, что все алфавиты конечны. Таким образом, хотя языки и могут содержать бесконечное число цепочек, но эти цепочки должны быть составлены из символов некоторого фиксированного конечного алфавита.1.5.4.
ÏðîáëåìûВ теории автоматов проблема — это вопрос о том, является ли данная цепочка элементом определенного языка. Как мы вскоре выясним, все, что называется “проблемой”в более широком смысле слова, может быть выражено в виде проблемы принадлежностинекоторому языку. Точнее, если Σ — некоторый алфавит, и L — язык в Σ, то проблема Lформулируется следующим образом.• Дана цепочка w из Σ*, требуется выяснить, принадлежит цепочка w языку L,или нет.Пример 1.26.
Задачу проверки простоты данного числа можно выразить в терминахпринадлежности языку Lp, который состоит из всех двоичных цепочек, выражающихпростые числа. Таким образом, ответ “да” соответствует ситуации, когда данная цепочкаиз нулей и единиц является двоичным представлением простого числа. В противномслучае ответом будет “нет”. Для некоторых цепочек принять решение довольно просто.Например, цепочка 0011101 не может быть представлением простого числа по той причине, что двоичное представление всякого целого числа, за исключением 0, начинается с1.
Однако решение данной проблемы для цепочки 11101 не так очевидно и требует значительных затрат таких вычислительных ресурсов, как время и/или объем памяти. 48Стр. 48ÃËÀÂÀ 1. ÀÂÒÎÌÀÒÛ: ÌÅÒÎÄÛ È ÏÎÍßÒÈßÎïèñàíèå ìíîæåñòâ êàê ñïîñîá îïðåäåëåíèÿ ÿçûêîâЯзыки часто задаются с помощью конструкции, описывающей множество:{w | сведения о w}.Читается данное выражение так: “множество слов w, соответствующих тому, что сказано о w справа от вертикальной черты”. Например:1. {w | w содержит поровну нулей и единиц}.2. {w | w есть двоичное представление простого числа}.3. {w | w есть синтаксически правильная программа на языке C}.Кроме того, часто вместо w пишут некоторое выражение, зависящее от параметров, иописывают цепочки языка, накладывая на эти параметры определенные условия.
Впервом из следующих примеров в качестве параметра фигурирует n, а во втором —параметры i и j.n n1. {0 1 | n ≥ 1}. Читается: “множество цепочек из n нулей и n единиц, где n большеили равно 1”. Этот язык содержит цепочки {01, 0011, 000111, …}. Заметим, что,как и для алфавита, мы можем определить n-ю степень одиночного символа какцепочку из n копий данного символа.i j2. {0 1 | 0 ≤ i ≤ j}.
Этот язык состоит из цепочек, у которых вначале идет некоторое(возможно, нулевое) число нулей, а затем некоторое число единиц, причем числопоследних не меньше числа нулей.В приведенном нами определении “проблемы” есть одно слабое место. Дело в том,что обычно под проблемами подразумевают не вопросы разрешения (истинно нечто, илинет), а запросы на обработку или преобразование некоторых входных данных (желательно, наилучшим способом). Например, задача анализатора в компиляторе языка С —определить, принадлежит ли данная цепочка символов ASCII множеству LC всех правильных программ на C — в точности соответствует нашему определению. Но в задачианализатора входят также формирование дерева синтаксического анализа, заполнениетаблицы имен и, возможно, другие действия.
Хуже того, компилятор в целом решает задачу перевода С-программы в объектный код для некоторой машины, и эта задача весьма далека от простого ответа “да” или “нет” на вопрос о правильности такой программы.Тем не менее, определение “проблем” как языков выдержало проверку временем ипозволяет нам успешно решать многие задачи, возникающие в теории сложности.
В рамках этой теории мы отыскиваем нижние границы сложности определенных задач. Особенно важны тут методы доказательства того, что определенные типы задач не могутбыть решены за время, меньшее по количеству, чем экспонента от размера их входныхданных.
Оказывается, что в этом смысле задача, сформулированная в терминах теорииязыков (т.е. требующая ответа “да” или “нет”), так же трудна, как и исходная задача,требующая “найти решение”.1.5. ÎÑÍÎÂÍÛÅ ÏÎÍßÒÈß ÒÅÎÐÈÈ ÀÂÒÎÌÀÒÎÂСтр. 4949Таким образом, если мы можем доказать, что трудно определить, принадлежит лиданная цепочка множеству LX всех правильных программ на языке X, следовательно, переводить программы с языка X в объектный код, по крайней мере, не легче. В самом деле, если было бы легко генерировать код, то мы могли бы попросту запустить транслятори, когда он успешно выработал бы объектный код, заключить, что входная цепочка является правильной программой, принадлежащей LX.
Поскольку последний шаг определения, выработан ли объектный код, не может быть сложным, то с помощью быстрого алгоритма генерации кода мы могли бы эффективно решать задачу о принадлежности цепочки множеству LX. Но так мы приходим к противоречию с предположением о том, чтоопределить принадлежность цепочки языку LX трудно. Итак, мы доказали методом отпротивного утверждение “если проверка принадлежности языку LX трудна, то и компиляция программ, написанных на языке X, также трудна”.Этот метод, позволяющий показать трудность одной задачи с использованием предполагаемого эффективного алгоритма ее решения для эффективного решения другой, заведомо сложной задачи, называется “сведением” второй задачи к первой. Это мощныйинструмент в исследованиях сложности проблем, причем его применение значительноупрощается в силу нашего замечания о том, что проблемами, по сути, являются лишь вопросы о принадлежности некоторому языку.×òî ýòî — ÿçûê èëè ïðîáëåìà?На самом деле, язык и проблема — это одно и то же.
Употребление терминов зависитлишь от нашей точки зрения. Когда нас интересуют цепочки сами по себе, например,множество {0n1n | n ≥ 1}, мы склонны видеть в этом множестве цепочек некоторыйязык. В последних главах этой книги мы будем больше интересоваться “семантикой”цепочек, т.е. рассматривать цепочки как закодированные графы, логические выражения или целые числа. В этих случаях нас будут больше интересовать не сами цепочки,а те объекты, которые они представляют. И тогда мы будем склонны рассматриватьмножество цепочек как некую проблему.Ðåçþìå♦ Конечные автоматы.
Конечные автоматы включают набор состояний и переходов между ними, зависящих от входных данных. Они весьма полезны припостроении различных систем программного обеспечения, включая лексические анализаторы компиляторов и системы проверки корректности схем илипротоколов.♦ Регулярные выражения. Это структурные записи для описания некоторых шаблонов, представимых конечными автоматами.
Используются во многих компонентах50Стр. 50ÃËÀÂÀ 1. ÀÂÒÎÌÀÒÛ: ÌÅÒÎÄÛ È ÏÎÍßÒÈßпрограммного обеспечения, например, в программах поиска по шаблону в текстахили среди файловых имен.♦ Контекстно-свободные грамматики. Эта важная система описания структурыязыков программирования и связанных с ними множеств цепочек используетсяпри построении такого компонента компилятора, как анализатор.♦ Машины Тьюринга. Автоматы, моделирующие все возможности реальных вычислительных машин. Позволяют изучать разрешимость, т.е. вопрос о том, что можнои чего нельзя сделать с помощью компьютера.
Кроме того, они позволяют отличать задачи, разрешимые за полиномиальное время, от неразрешимых.♦ Дедуктивные доказательства. Основной метод доказательства, состоящий из цепочки утверждений, которые либо даны как истинные, либо логически следуют изпредыдущих утверждений.♦ Доказательства утверждений типа “если-то”.
Многие теоремы имеют вид:“если (нечто одно), то (нечто другое)”. Утверждение (или утверждения), стоящее вскобках после “если”, является гипотезой, а утверждение, стоящее после слова“то”, — заключением. Цепочка дедуктивных доказательств утверждений этого типа начинается с гипотезы, из которой последовательно логически выводятся новые утверждения до тех пор, пока на каком-то шаге одно из них не совпадет с заключением.♦ Доказательства утверждений типа “тогда и только тогда”.
Существуют теоремы вида “(нечто одно) тогда и только тогда, когда (нечто другое)”. Доказываются такие утверждения в одну и другую стороны как утверждения типа “если-то”.Этот вид теорем очень близок к утверждениям о равенстве двух множеств, записанных разными способами. Для их доказательства нужно показать, что каждое изэтих множеств содержится в другом.♦ Доказательство контрапозиции. Доказать утверждение типа “если H, то C” иногда бывает легче путем доказательства эквивалентного утверждения “если не C, тоне H”, которое называют контрапозицией исходного.♦ Доказательство методом “от противного”.
В некоторых случаях удобнее вместо утверждения “если H, то C” доказывать утверждение “если H и не C, то (нечтозаведомо ложное)”. Этот метод доказательства называется доказательством отпротивного.♦ Контрпримеры. Иногда необходимо доказывать, что некоторое утверждение неявляется истинным. Если это утверждение содержит один или несколько параметров, то можно доказать его ложность в целом, приведя всего один контрпример,т.е. подобрав такие значения параметров, при которых это утверждение ложно.ÐÅÇÞÌÅСтр. 5151♦ Индуктивные доказательства.
Утверждения, содержащие целый параметр n,очень часто могут быть доказаны по индукции. Для этого мы доказываем, чтоданное утверждение истинно для базиса, конечного числа случаев определенныхзначений n. Затем доказываем, что если утверждение истинно для n, то оно истинно и для n + 1.♦ Структурная индукция. Довольно часто в этой книге возникает ситуация, когда втеореме, требующей индуктивного доказательства, речь идет о таких рекурсивноопределяемых понятиях, как деревья.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
