Главная Промышленная автоматика.

О И 1, больше множества целых чисел. Указание: Возьмите однозначное десятичное представление вещественных чисел. Предположите от противного, что указанные множества равномощны. Тогда можно найти последовательность вещественных чисел г, Гц, которая содержит все вещественные числа 0<г<1. Можете ли Вы найти вещественное число г между О и I, которое отличается в г-м знаке от Г;, каково бы ни было 1?

*0Л.23. Пусть -линейный порядок на конечном множестве Л. Покажите, что существует такой единственный элемент аА, что aRb для всех ЬА - {а}. Этот элемент а называется наименьшим. Если Л бесконечно, всегда ли существует наименьший элемент?

*0.1.24. Покажите, что {а, {а, Ь}}{с, {с, d}} тогда и только тогда, когда а = с и b-d.

0.t,25. Пусть R - частичный порядок на множестве А. Покажите, что если aRb, то bRa ложно.

*0.1.2б. Используйте аксиомы об объединении множеств и о множестве всех подмножеств для того, чтобы показать, что если А и В-множества, то Лхб - множество.

**0.1.27. Покажите, что каждое множество либо конечно, либо бесконечно, но не то и другое вместе.

*0Л.28. Покажите, что каждое счетное множество бесконечно.

*0Л.29. Покажите, что следующие множества равномощны:

(1) множество вещественных чисел между О и 1,

(2) множество всех вещественных чисел,

(3) множество всех отображений целых чисел в целые числа,

(4) множество всех подмножеств положительных целых чисел.

**0.1.30. Покажите, что [Л) всегда больше Л для любого множества Л.

0.1.31. Покажите, что если R - частичный порядок на множестве Л, то отношение RR\j{{a, а)\аА} является рефлексивным частичным порядком на Л.

0.1.32. Покажите, что если / - рефлексивный частичный порядок на множестве Л, то отношение R = R~~{(а, а)\аА} является частичным порядком на Л.

0.2. МНОЖЕСТВА ЦЕПОЧЕК

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

0.2, МНОЖЕСТВА ЦЕПОЧЕК

0.2.1 • Цепочки

Прежде всего нам необходимо понятие алфавита. Алфавитом мы будем называть любое множество символов. Предполагается, что термин „символ" имеет достаточно ясный интуитивный смысл и не нуждается в дальнейшем пояснении.

Алфавит не обязан быть конечным и даже счетным, но во всех практических приложениях он будет конечным. Два примера алфавитов: множество, состоящее из 26 прописных и 26 строчных латинских букв (латинский алфавит), и множество {О, 1}, часто называемое бинарньш или двоичньш алфавитом.

Термины буква н знак будут использоваться как синонимы термина символ для обозначения элемента алфавита. Если написать последовательность символов, располагая их один за другим, то получится цепочка символов. Например, ОЮИ-цепочка в бинарном алфавите {О, 1(. Термины слово и строка (а иногда, особенно при лингвистических интерпретациях, предложение) часто используются как синонимы термина цепочка.

Существует одна цепочка, которая часто встречается и потому имеет специальное обозначение. Это пустая цепочка, обозначаемая символом е. Пустая цепочка не содержит ни одного символа.

Соглашение. Обычно мы будем прописными греческими буквами обозначать алфавиты. Буквы а, Ь, с и d будут обозначать отдельные символы, а буквы t, и, v,w, х, у и г, вообще говоря, будут обозначать цепочки символов. Цепочку, состоящую из i символов а, будем обозначать а. Например, аа), а" = аа, а = ааа н т.д. Тогда а" - пустая цепочка е.

Определение. Формально цепочки в алфавите 2 определяются следующим образом:

(1) е-цепочка в 2,

(2) если X-цепочка в 2 н all, то ха - цепочка в 2,

(3) у-цепочка в 2 тогда и только тогда, когда она является таковой в силу (1) или (2).

Определим операции Над цепочками, которые понадобятся Нам в дальнейшем. Если х и - цепочки, то цепочка ху называется конкатенацией (или сцеплением) х и у. Например, если х~аЬ и y = cd, то xy = abcd. Для любой цепочки х всегда хе ~ сх X.

Обращением цепочки х (обозначается д:) называется цепочка л:, записанная в обратном порядке, т. е. если ха.. .а,„ где все а-символы, то х = а.. .а. Кроме того, е = е.

1) Мы отождествляем, таким образом, символ а с цепочкой, состоящей из одного символа а.



0.2.2. Языки

Определение. Языком в алфавите 2 называется множество цепочек в 2. Под это определение, конечно, подходит почти любое понятие языка. Фортран, Алгол, ПЛ/1 и даже английский язык охватываются этим определением.

Пример О.Ю. Рассмотрим простые примеры языков в алфавите X. Пустое множество 0--гто язык. Множество {е}, содержащее только пустую цепочку, тоже является языком. Заметим, что 0 и {е}~лва различных языка. □

Определение. Обозначим через 2* множество, содержащее все цепочки в алфавите 2, включая е. Например, если 2 -бинарный алфавит {О, тб

Х* = {е, О, 1, 00, 01, 10, И, ООО, 001, ...}

Каждый язык в алфавите 2 является подмножеством множества 2*. Множество всех цепочек в 2, за исключением е, обозначается 2 + .

Пример 0.11. Рассмотрим язык L, содержащий все цепочки из нуля или более символов й. Его Можно обозначить \a\iO}. Ясно, что L = {a\*. Q

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

В соответствии с этим соглашением а*{а}*.

Определение. Если язык L таков, что никакая цепочка в L не является собственным префиксом (суффиксом) никакой другой

цепочки в L, то говорят, что L обладает префиксным (суф-фиксным) свойством.

Например, й!* не обладает префиксным свойством, а {ab \ 0} обладает.

0.2.3. Операции над языками

Нам часто будут нужны различные операции над языками. Сейчас мы рассмотрим основные из них.

Так как язык-это множество, то операции объединения, пересечения, нахождения разности и дополнения применимы и к языкам. Операцию конкатенации можно применять к языкам так же, как к цепочкам.

Определение. Пусть L -язык в алфавите 2, а -язык в алфавите 23. Тогда язык Lj L, называемый конкатенацией (а также сцеплением или произведением) языков и 1,~это язык {xy\xL и yLi\.

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

Определение. Итерация языка L, обозначаемая через L*, определяется следующим образом:

(1) L = {e},

(2) L«-LL"~i для /1> 1.

(3) L*=- и L"-

л > о

Позитивная итерация языка L, обозначаемая через это

язык и Заметим, что L"- = Ш = С*Ь и L* = L+U{€}.

п > 1

Нас будут также интересовать отображения, определенные на языках. Примером отображения, которое часто встречается при работе с языками, служит гомоморфизм. Его можно определить так:

Определение. Пусть 2 и 2з -алфавиты. Гомоморфизмом называется любое отображение Н: 2~>22. Область определения гомоморфизма h можно расширить до 2i, полагая 1г{е)=е и h {ха) = h {х) h {а) для всех xl и aSj.

Применяя гомоморфизм к языку L, мы получаем другой язык h{L), который представляет собой множество цепочек {h {w)\wL\.

Пример 0.12. Допустим, что мы хотим заменить каждое вхождение в цепочку символа О на символ а каждое вхождение 1

Пусть X, у и 2-произвольные цепочки в некотором алфавите 2. Назовем л: префиксом цепочки ху, а у-суффиксом цепочки ху. Цепочку у назовем подцепочкой цепочки хуг. Префикс и суффикс цепочки являются ее подцепочками. Например, Ьа - префикс и подцепочка цепочки Ьас. Заметим, что пустая цепочка является префиксом, суффиксом и подцепочкой любой цепочки.

Если хфу ц префикс (суффикс) цепочки у, то х называется собственным префиксом (суффиксом) цепочки у.

Длина цепочки-это число символов в ней, т. е. если ха ... а„, где все ai - символы, то длина цепочки х равна п. Длину цепочки х будем обозначать \х\. Например, \ааЬ\ = 3 и I е 1 0. Все цепочки, с которыми нам придется встречаться, будут конечной длины.



Обратите внимание, что {012}* не то же самое, что {0,J,2}*.

(а) 0,

(б) {е}, ,

(в) {а"ЬЧп 1},

(г) L*, если L обладает префиксным свойством,

(д) {w\w{a, Ь}* и число символов а в w равно числу символов Ь\.

0.3. НЕКОТОРЫЕ ПОНЯТИЯ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

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

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

0.3.1. Доказательства

Формальную математическую систему можно охарактеризовать с помощью следующих основных компонент:

(1) основные символы,

(2) правила образования,

(3) аксиомы,

(4) правила вывода.

Множество основных символов содержит символы для обозначения констант, операторов и т. д. В соответствии с правилами образования из этих основных символов строятся утверждения. Затем определяются примитивные утверждения, справедливость которых принимается без доказательства. Эти утверждения называются аксиомами системы.

Далее задаются правила, посредством которых из справедливых утверждений можно выводить новые справедливые утверждения. Такие правила называются правилами вывода.

Если требуется доказать, что некоторое утверждение истинно в некоторой формальной системе, то доказательством этого утверждения будет такая последовательность утверждений, что

(I) кал<дое утверждение либо является аксиомой, либо его можно получить из одного или более предыдущих утверждений с помощью правила вывода;

на bb. Тогда можно определить гомоморфизм Л так, что Н{0) = й и h{\)bb. Если L = {0"l«n> 1}, то /г (L) = л > 1}. □

Хотя гомоморфизмы не всегда взаимно однозначны, часто бывает полезно говорить об их обращениях (как отношениях).

Определение. Если h: 2-.-з - гомоморфизм, то отношение /": 2з->.(21), определенное ниже, называется обращением гомоморфизма. Если yl, roh~4y) - Это множество цепочек в алфавите 2,, которые отображаются гомоморфизмом h в цепочку г/, т. е. h~ (у) {x\h (х) = у]. Если L - язык в S, то Л - я.зык в 2j, состоящий из тех цепочек, которые h отображает в цепочки из L. Формально h~{L) U {у) = {x\h {х) L).

Пример 0.13. Пусть /[ - гомоморфизм, для которого /i(0) -а и h{\) = a. Тогда /i-i(«)-{0, 1} и h~{if){{), \]\

В качестве второго примера возьмем такой гомоморфизм /i, что /i(0)-« и /?,(1)-£. Тогда/1-(с)=-1* и h (а) Здесь

1*01* обозначает язык {101-ц /0J-; это согласуется с нашими определениями и соглашением, отождествляющим а с {а). □

УПРАЖНЕНИЯ

0.2.1. Выпишите все (а) префиксы, (б) суффиксы и (в) подцепочки цепочки аЬс.

0.2.2. Докажите или опровергните, что L=L* - \е\. 0.2.3. Пусть h - гомоморфизм, определенный равенствами h{Q) = a, h{\)bb и h{2)e. Опишите язык h{L), где 1-012}*).

0.2.4. Пусть гомоморфизм h тот же, что и в упр. 0.2.3. Опишите язык Н~{{аЬУ).

*0.2.5. Докажите или опровергните следующие утверждения:

(б) h{hrHL))-=L.

0.2.6. Может ли язык L* или быть пустым? При каких условиях L* и L конечны?

*0.2.7. Постройте полные порядки на следующих языках: (а) {а, Ь}\

(в) \w\w\a, b}* и число символов а в w равно числу символов Ь].

0.2.8. Какие из следующих языков обладают префиксным (суффнксным) свойством:





0 1 2 [3] 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.002