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

ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ АВТОМАТОВ 1.5.1. Алфавиты Алфавитом называют конечное непустое множество символов. Условимся обозначать алфавиты символом Х. Наиболее часто используются следующие алфавиты. 1. Х = !0,11 — бинарный или двоичный алфавит. 2. Х = 1и, Ь, ..., г! — множество строчных букв английского алфавита. 3. Множество АБС!1-символов или множество всех печатных АБС!1-символов. 1.5.2. Цепочки Цепочка, нли иногда слово, — это конечная последовательность символов некоторого алфавита. Например, 01101 — это цепочка в бинарном алфавите Х = 10, 1!. Цепочка 111 также является цепочкой в этом алфавите.

Пустая цепочка Пустая цеиочка — это цепочка, не содержащая ни одного символа. Эту цепочку, обозначаемую в, можно рассматривать как цепочку в любом алфавите. Длина цепочки Часто оказывается удобным классифицировать цепочки по их длине, т.е. по числу позиций для символов в цепочке. Например, цепочка 01101 имеет длину 5. Обычно говорят, что длина цепочки — это "число символов" в ней. Это определение широко распространено, но не вполне корректно. Так, в цепочке 01101 всего 2 символа, но число нозиНий в ней — пять, поэтому она имеет длину 5.

Все же следует иметь в виду, что часто пишут "число символов", имея в виду "число позиций". Длину некоторой цепочки н обычно обозначают ~н!. Например, !011! = 3, а !е! = О. Степени алфавита Если Х вЂ” некоторый алфавит, то можно выразить множество всех цепочек определенной длины, состоящих из символов данного алфавита, используя знак степени.

Определим Х как множество всех цепочек длины к, состоящих из символов алфавита Х. Пример 1.24. Заметим, что Х~ = (в! независимо от алфавита Х, т.е. в — единственная цепочка длины О. Если Х = 10, 11, то Х' = 10, 11, Х' = 100, 01, 1О, 111, Х' = 1000, 001, 010, 011, 100, ! 01, 110, 1!1! и так далее. Отметим, что между Х и Х' есть небольшое различие. Дело в том, что Х есть алфавит, и его элементы 0 и ! являются символами, а Х является множеством цепочек, и его элементы — это цепочки 0 и 1, каждая длиной 1. Мы не будем вводить разные обозначения для этих множеств, полагая, что из контекста будет понятно, является !О, 11 или подобное ему множество алфавитом или же множеством цепочек. П ГЛАВА 1. АВТОМАТЫ: МЕТОДЫ И ПОНЯТИЯ 46 Соглашения о символах и цепочках Как правило, строчными буквами из начальной части алфавита (или цифрами) мы будем обозначать символы, а строчными буквами из конца алфавита, например тт, х, у или х — цепочки.

Руководствуясь этим соглашением, вы легко сможете понять, элементы какого типа рассматриваются в том нли ином случае. Множество всех цепочек над алфавитом Х принято обозначать Х . Так, например, !0,1) = (е, О, 1, 00, 01, 10, 11, 000, ...). По-другому это множество можно записать в виде Х =Х !)Х !)Х О...

Иногда нам будет необходимо исключать из множества цепочек пустую цепочку. Множество всех непустых цепочек в алфавите Х обозначают через Х'. Таким образом, имеют место следующие равенства; ° Х- Х1ОХг!)Хз!) Х = Х'О !в). Конкантенация цепочек Пусть х и у в цепочки. Тогда ху обозначает их конкатенацию (соединение), т.е.

цепочку, в которой последовательно записаны цепочки х и у. Более строго, если х — цепочка из г символов: х = агаг...а„ а у — цепочка изг символов: у = Ьгбг...Ь„ то ху — это цепочка длины г ь у: ху = а,а,... а Ь,Ь,... Ь, Пример 1.25. Пусть х = 01! 01 и у = 1! О. Тогда ху = 01101110, а ух = 11001101. Для любой цепочки н справедливы равенства ви = н в = зе. Таким образом, в является единицей (нейтральным элементом) относительно операции конкантенации, поскольку результат ее конкатенации с любой цепочкой дает ту же самую цепочку (аналогично тому как О, нейтральный элемент относительно сложения, при сложении с любым числом х дает число х). Сг 1.5.3, Языки Множество цепочек, каждая из которых принадлежит Х*, где Х вЂ” некоторый фиксированный алфавит, называют языком .

Если Х вЂ” алфавит, и Ь ~ Х, то Ь вЂ” это язык над г Х, или в Х. Отметим, что язык в Х не обязательно должен содержать цепочки, в которые входят все символы Х. Поэтому, если известно, что Ь является языком в Х, то можно утверждать, что Х вЂ” это язык над любым алфавитом, содержащим Х. Термин "язык" может показаться странным.

Однако оправданием служит то, что и обычные языки можно рассматривать как множества цепочек. Возьмем в качестве при- В таком определении язык часто называется формальным. — Прим. ред. 1.6. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ АВТОМАТОВ 47 мера английский язык, где набор всех литературных английских слов есть множество цепочек в алфавите (английских же букв). Еще один пример — язык программирования С или любой другой язык программирования, в котором правильно написанные программы представляют собой подмножество множества всех возможных цепочек, а цепочки состоят из символов алфавита данного языка. Этот алфавит является подмножеством символов АЗС!!. Алфавиты для разных языков программирования могут быть различными, хотя обычно они состоят из прописных н строчных букв, цифр, знаков пунктуации и математических символов.

Существует, однако, множество других языков, изучаемых в теории автоматов. Приведем несколько примеров. 1. Язык, состоящий из всех цепочек, в которых и единиц следуют за и нулями для некоторого и > О: (К 01, 0011, 0001! 1, ... ). 2. Множество цепочек, состоящих нз 0 и 1 и содержащих поровну тех и других: !е, 01, !О, 00!1, 1001, ...). 3. Множество двоичных записей простых чисел: !10, 1!, 101, 111,1011, 4. Х вЂ” язык для любого алфавита Е. 5. Я вЂ” пустой язык а любом алфавите. б.

(е) — язык, содержащий одну лишь пустую цепочку. Он также является языком в любом алфавите. Заметим, что !2! и !я); первый не содержит вообще никаких цепочек, а второй состоит нз одной цепочки. Единственное существенное ограничение для множеств, которые могут быть языками, состоит в том, что все алфавиты конечны. Таким образом, хотя языки и могут содержать бесконечное число цепочек, но эти цепочки должны быть составлены из символов некоторого фиксированного конечного алфавита.

1.5.4. Проблемы В теории автоматов проблема — зто вопрос о том, является ли данная цепочка элементом определенного языка. Как мы вскоре выясним, все, что называется "проблемой" в более широком смысле слова, может быть выражено в виде проблемы принадлежности некогорому языку. Точнее, если Š— некоторый алфавит, и Ь вЂ” язык в Х, то проблема Ь формулируется следующим образом. ° Дана цепочка зг из Х', требуется выяснить, принадлежит цепочка в языку Т., илн нет. Пример 1.26. Задачу проверки простоты данною числа можно выразить в терминах принадлежности языку Ь„который состоит из всех двоичных цепочек, выражающих простые числа.

Таким образом, ответ "да" соответствует ситуации, когда данная цепочка нз нулей и единиц является двоичным представлением простого числа. В противном ГЛАВА 1. АВТОМАТЫ: МЕТОДЫ И ПОНЯТИЯ 48 случае ответом будет "нет". Для некоторых цепочек принять решение довольно просто. Например, цепочка 0011101 не может быть представлением простого числа по той причине, что двоичное представление всякого целого числа, за исключением О, начинается с 1. Однако решение данной проблемы для цепочки 11101 не так очевидно и требует значительных затрат таких вычислительных ресурсов, как время и/нли объем памяти.

П Описание множеств как способ определения языков Языки часто задаются с помощью конструкции, описывающей множество: (гг ! сведения о и ). Читается данное выражение так: "множество слов ю, соответствующих тому, что сказано о в справа от вертикальной черты". Например: 1, (и ~ ж содержит поровну нулей и единиц). 2. (и ~ в есть двоичное представление простого числа). 3. (ж ! ж есть синтаксически правильная программа на языке С).

Кроме того, часто вместо ч пишут некоторое выражение, зависящее от параметров, и описывают цепочки языка, накладывая на эти параметры определенные условия. В первом из следующих примеров в качестве параметра фигурирует п, а во втором— параметры! и ! 1.

(О"1 ~ и > 1). Читается: "множество цепочек из и нулей и л единиц, где и больше или равно 1". Этот язык содержит цепочки (01, 0011, 000111, ... ). Заметим, что, как и для алфавита, мы можем определить л-ю степень одиночного символа как цепочку из л копий данного символа. 2. (О'1 (0 <! ъу). Этот язык состоит из цепочек, у которых вначале идет некоторое (возможно, нулевое) число нулей, а затем некоторое число единиц, причем число последних не меньше числа нулей. В приведенном нами определении "проблемы'* есть одно слабое место. Дело в том, что обычно под проблемами подразумевают не вопросы разрешения (истинно нечто, или нет), а запросы на обработку или преобразование некоторых входных данных (желательно, наилучшим способом).

Например, задача анализатора в компиляторе языка С— определить, принадлежит ли данная цепочка символов АБСН множеству Тс всех правильных программ на С вЂ” в точности соответствует нашему определению. Но в задачи анализатора входят также формирование дерева синтаксического анализа, заполнение таблицы имен и, возможно, другие действия. Хуже того, компилятор в целом решает задачу перевода С-программы в объектный код для некоторой машины, и эта задача весьма далека от простого ответа "да" или "нет" на вопрос о правильности такой программы. Тем ие менее, определение "проблем" как языков выдержало проверку временем и позволяет нам успешно решать многие задачи, возникающие в теории сложности. В рамках этой теории мы отыскиваем нижние границы сложности определенных задач.

Осо- 1.5. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ АВТОМАТОВ 49 бенно важны тут методы доказательства того, что определенные типы задач не могут быть решены за время, меньшее по количеству, чем экспонента от размера их входных данных. Оказывается, что в этом смысле задача, сформулированная в терминах теории языков (т.е. требующая ответа "да" или "нет"), так же трудна, как и исходная задача, требующая "найти решение'*. Таким образом, если мы можем доказать, что трудно определить, принадлежит ли данная цепочка множеству Ех всех правильных программ на языке Х, следовательно, переводить программы с языка Х в объектный код, по крайней мере, не легче.