Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 5
Текст из файла (страница 5)
Обозначим (1) А'= А, (2) А'=-А' 'хА для ! ) 1. Пусть Аь обозначает множество О А'. .1 0.1.13. Пусть )? — полный порядок на А. Определим отноше- ние )? на А', положив (а„..., а,„) Я (Ь„..., Ь„) тогда н только тогда, когда выполняется одно из двух условий'); ') Строго говоря, (а„..., аа) означает ((...((аь ая), ая),,), а ) в со. ответствен с определением Аа. 2В (1) аЯЬе для некоторого ! -т и а --Ь,. для всех 1 ' ! < с, (2) т и и а,=--Ь, для всех 1 «(«т. Покажите, что Я вЂ” полный порядок на А . Он называется лексикографическил> порядком на А", (Примером лскснкографического порядка может служить упорядочение слов в словаре.) 0.1.16. Для каждого из следующих отношений установить, является ли оно частичным порядком, рефлсксивпым частичным порядком, линейным порядком или рефлексивным линейным порядком: (а): — на У (А), (б) ~ на У(А), (в) отношение Я, на множестве людей П, определенное так: а)?,Ь тогда и только тогда, когда а — отец Ь, (г) отношение )(, на Н, определенное так: айяЬ тогда и только тогда, когда а — предок Ь, (д) отношение Яя на Г>, опРеделениое так: айяЬ тогда и только тогда, когда а старше Ь.
0,1.17. Пусть )к> и )?,— отношения. Компози>(ие>! отношений )?, и >с„обозначаемой Й> о )?в, назь>вается отношение ((а, Ь)) существует такое с, что аЯ,с и сй>,Ь). Покажите, что если Я, н )?я — отображения, то )?> о )?я — отображение. При каких условиях )?, о )?, будет всюду определенным отображением? Инъективным отображением? Биективным отображением? 0.1.18. Пусть А — конечное множество и Вс- "А. Пока>ките, что если М: А —  — биективное отображение, то А =В.
0.1,19. Пусть А и В состоят соответственно из т и и элементов. Покажите, что существует и всюду определенных на А функций, отображающих А в В. Сколько существует всех не обязательно всюду определенных отображений из А в В? *0.1.20. Пусть А — произвольное не обязательно конечное множество. Покажите, что множества У(А) и (М) М вЂ” всюду определенная функция, отображающая А в (О, 1)) равномощпы. 0.1.21. Покажите, что множество всех целых чисел равно- мощно (а) множеству простых чисел, (б) множеству пар целых чисел. Указание; Определите линейный порядок )? на множестве пар целых чисел, положив ((„)>) )? (>'„),) тогда и только тогда, когда (>+)> <(я+)я илн (,+)> -(,+)я и (, <с,, 0.1.22.
Множестно А „больп>е" множества В, если А и В имеют разную мощность и В равиомощно подмножеству множества А. Покажите, что множество вещественных чисел, лежащих строго между 25 гл. е. ИРВдВАРитнльныи Агдтамдтическив снеди ния о.г. множествд пвпочвк 0.2,1. Цепочки плие: озьмите одно- 0 и 1, больше множества целых чисел. Указана: В значное десятичное представление веще тв чисел.
П положите от п отивного, что ественных чисел. П е тв' чисел. Предр вного, что указанные множества равиомогцны. сть вещественных чисел г„ огда можно найти последовательность веще Можете ли В г„..., которая содержит все вещественные числа 0< <1. ы найти вещественное число г между 0 и 1, кото ое отличается в г'-м знаке от г, каково бь б '? о ы ни было г? *0.1.23.
П сть ?? — л * *... у —, инейный порядок иа конечном множе- стве А. Покажите, что с еств е угц уст такой динственный элемент а , что агг для всех Ь Е А — (а). Этот эле наименьигим. Если А б емент а называется ший элемент? есконечио, всег а ли с уществует иаимень- тогта ког = Ь =г( 0.1.26. Пусть Я вЂ частичн по я ок на р до на множестве А 1Ююи а, то ??а ложно. *0.1.26.
Использ йте А ИВв множестве всех по, у" аксиомы об объединении множеств и дмиожеств для того, чтобы показать, что если о и  — множества, то А х — множество. баск е*0.1.27, Покажите чт о каждое множество либо конечно, либо есконечно, но не то и другое вместе. *0.1.26. Пока * ..' . жите, что каждое счетное множество бесконечно. "0.1.29. Покажите, что сле (1) ми дующие множества равномощны: ( ) множество вещественных чисел меж 0 1, ду н ( ) множество всех вещественных чи е,, (, ) .
ножество всех отображений целых ч ых чисел в целые числа, ( ) множество всех подмножеств положите т гте. ьных целых чисел. *"0.1.30. Покажите, что Ьь(А) всег множества А. ' г ) сегда больше А для любого 0.1.31. Покажите, , что если ?? — частичный порядок на мно- 0.1.32. Покажите, чт , что если 7? — рефлексивный частичный по- рядок на множестве А, то отношение ??'=ге — ((, )~ ' 1 ляется частичным порядком иа А. — ( а, а аЕА1 яв- 0.2. МНО1КЕСТВА ЦЕПОЧЕК мпож ' В этой книге мы будем заниматься главгы б г м о разом такими В настоя ествами, элементами которых служат служат цепочки символов, почками.
настоящем разделе мы определим термины, ы, связанные с це- Прежде всего нам необходимо понятие алфавита. Алфавитом мы будем называть любое множество символов. Предполагается, что термин „символ" имеет достаточно ясный интуитивный смысл и не нуждается в дальнейшем пояснении. Алфавит не обязан быть конечным и даже счетным, но во всех практических приложениях он будет конечным. Два примера алфавитов: множество, состоящее из 26 прописных и 26 строчных латинских букв (латинский алфавит), и мпожество (О, 1), часто называемое бинарным или дашчным алфавитом, Термины буква и знак будут использоваться как синонимы термина сиивсл для обозначения элемента алфавита. Если написать последовательность символов, располагая их один за другим, то получится цепочка символов, Например, 01011 — цепочка в бинарном алфавите (О, 1).
Термины слово и строка (а иногда, особенно при лингвистических интерпретациях, предложение) часто используются как синонимы термина цепочка. Существует одна пеночка, которая часто встречается и потому имеет специальное обозначение. Это пустая цепочка, обозначаемая символом е.
Пустая цепочка не содержит ии одного символа. Соглашение. Обычно мы будем прописными греческими буквами обозначать алфавиты. Буквы а, Ь, с и г( будут обозначать отдельные символы, а буквы Т, и, о, ш, х, у и г, вообще говоря, будут обозначать цепочки символов. Цепочку, состоящую из г' символов а, будем обозначать и'. Например, а"=а '), аз=оп, а'=ааа и т. д. Тогда а' — пустая цепочка е. Определение. Формально цепочки в алфавигпе Х определяются следующим образом: (1) е — цепочка в Х, (2) если х — цепочка в Х и аЕХ, то ха — цепочка в Х, (3) у — цепочка в Х тогда и только тогда, когда она является таковой в силу (1) или (2).
Определим операции над цепочками, которые понадобятся нам в дальнейгпем. Если х и у — цепочки, то цепочка ху называется конкатенацией (или сцеплением) х и у. Например, если х=-аЬ и у — — сс(, то ху=-аЬсс(. Для любой цепочки х всегда хе = ех=х. Обрагцением цепочки х (обозначается хл) называется цепочка х, записанная в обратном порядке, т. е. если х — — п,...ав, где все а,— символы, то хи=а,...аг. Кроме того, ел=в. ') г"гы отождествляем, таким образом, символ а с цепочкой, состоящей из одного символе а. 27 ГЛ В. ПРЕДВАРИТЕЛЬНЫЕ МАТЕМАТИЧЕСКИЕ СВЕДЕНИЯ Охс МНОЖЕСТВА ЦЕПОЧЕК Пусть х, у и г — произвольные цепочки в некотором алфавите Х. Назовем х префиксом цепочки ху, а у — суффиксом цепочки ху.
Цепочку у назовем подцепочкой цепочки хуг. Префикс и суффикс цепочки являются ее подцепочками. Например, пав префикс и подцепочка цепочки (!ас. Заметим, что пустая цепочка является префиксом, суффиксом и подцепочкой любой цепочки. Если хну и х †префи (суффикс) цепочки у, то х называется собственным префиксом (суффнксом) цепочки у. Длина цепочки †э число символов в ней, т. е. если х=а, ... а„, где все а! — символы„то длина цепочки х равна п. Длину цепочки х будем обозначать )х). Например, ~ааЬ(=-3 и (е(=-О. Все цепочки, с которыми нам придется встречаться, будут конечной длины. 6.2.2. Языии Определение. Языком в алфавите Х называется множество цепочек в Х.
Под это определение, конечно, подходит почт! л бое понятие языка. Фортран, Алгол, ПЛ)! и даже английский ю язык охватываются этим определением. Пример 0,10. Рассмотрим простые примеры языков в алфавите Х. Пустое множество яз--это язык. Мпожсство (е), содержащее только пустую цепочку, тоже является языком. Заметим„ что Я и (е) — два различных языка. С) Определение. Обозначим через Хл множество, содержащее все цепочки в алфавите Х, включая е. Например, если Х вЂ” бинарный алфавит (О, 1), то Х*=(е, О, 1, 00, 01, 10, 11, 000, 001, ...) Каждый язык в алфавите Х является подмножеством множества Х*.
Множество всех цепочек в Х, за исключением е, обозначается Х'!. Пример О.11. Рассмотрим язык А,„содержащий все цепочки из нуля или более символов а. Его можно обозначить (а' ( В~ О). Ясно, что Е!=(а)'. [З Соглашение. В тех случаях, когда это не может привести к путанице, мы часто будем обозначать множество, состоящее из одного элемента, самим этим элементом. В соответствии с этим соглашением а*=-(а)'. Определение. Если язык А таков, что никакая цепочка в Е не является собственным префиксом (суффнксом) никакой другой 2В цепочки в Ь, то говорят, что Ь обладает префиксным 1суффиксным) свойством.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
