Теория синтаксического анализа, перевода и компиляции - Том 1 (Теория синтаксического анализа, перевода и компиляции), страница 6

Например, а' не обладает префикспым свойством, а (а!о ( ! . О) обладает. 0.2.3. Операции над язынами Нам часто будут нужны различные операции над языками. Сейчас мы рассмотрим основные из них. Так как язык---это множество, то операции объединения, псресечения, нахождения разности и дополнения применимы и к языкам. Операцию конкатенации можно применять к языкам так же, как к цепочкам. Определение. Пусть Ь! — язык в алфавите Х„а !'.,— язык в алфавите ХВ.

Тогда язык Ь!Ь„называемый конкатенацией (а также сцеплением или произведением) языков Ь, и А„— это язык (ху(хЕ!'., и уЕ(,,). В некоторых случаях нам нужно будет образовать сцепления произвольного числа цепочек из языка, Эта ситуация охваты- вается понятием итерации языка. Определение. Итерация языка 1., обозначаемая через определяется следующим образом: (1) 1,' = (е), (2) (."=.Ы." ' для п ь 1, (3) А"= 0 л>0 Иозип!ивная итерация языка 1.„обозначаемая через Е+,— это язык 0 !.". Заметим, что Е+ = Ы,*= ~;!'. и Ь'= Ь" 0 (е).

л" 1 Нас будут также интересовать отображения, определенные на языках. Примером отображения, которое часто встречается при работе с языками, служит гомоморфизм. Его можно определить так: Определение. Пусть Х! и Х,— алфавиты. Гомоморфизмом называется любое отображение й: Х! — Х;. Область определения гомоморфизма и можно расши(!Ить до Х;, полагая Й(е)=е и й (ха) = Ь (х) и (а) для всех х Е Х! и а Е Х!. Применяя гомоморфизм к языку 1-, мы получаем другой язык й (С), который представляет собой множество цепочек (й ( в) ~ и! Е Ц.

Пример 0.12. Допустим, что мы хотим заменить каждое вхождение в цепочку символа 0 на символ а, а каждое вхождение 1 29 УПРАЖНЕНИЯ О.ЗЛ. Доказательства 3! гл. 0. пиедвлиитвльные мхтеметичискии свидания ий 1 =ЬЬ. Если = л на ЬЬ. Тогда можно определить гомоморфизм й, ! (О =- ( )= . сли Е=(0"1" (!!~1), то й(Е)=(аей'"~п'"Г1), ! ! так, что Г( ) = а Хотя гомоморфизмы не всегда взаим но однозначны, часто бывает полезно говорить об их обрап е 1 ниях (как отношениях). Х; — У (Х,*), определенное ниже, называет . — ется обраи!внаем голГО- вите „которые отображаются гомоморфизмом й в цепочку у, т.

е. й ' (у) = (х ! й (х) = у) . Если Š— язык в В„то I! ! (Е) — язык в Х„состояп!Ий из тех цепочек, котор й бр почки из Е. Формально й '(й)=: 0 й ' )=( то ые ото ражает в е(у) = (х ~ й (х) Е Ц. Пример 0.13. Пусть й — гомоморфизм, для кото ого й (0) =а и й (!) =-а. Тогда й '(а) = (О, !) и й !(и*)=-(О, 1)*. чтой О-- В качестве вто ого р примера возьмем такой гомоморфизм й, что (О)--а и й(1)=е. Тогдай '(е)=1* и й '(а) —.1"01'. 3 ! "01* обозначает язык (!'01Г,!Г, "= О,', это с О... .2.1. Выпишите все (а) префиксы, (б) с фф цепочки цепочки иЬс.

( ) суффиксы и (в) под- 0.2.2. .2.2. Докажите или опровергните, что Т.'=Е' — (е). 0.2.3. Пусть й — гомомо физ рфизм, определенный равенствами ( )=-а, ( )=ЬЬ и й(2)=е. Опишите язык й(Е), гдето=(0!2)''). 0.2.4. Пусть гомоморфизм й тот же, что и в Опишите язык й '((аЬ)'). . е, что и в упр. 0.2.3. *0.2.5. Докажите или (а) й-' (й (Е)) = Е, опровергните следующие утверждения: (б) й (й.

' (Ц) =-= Е. 0.2.6. М Может лн язык Е' или Е' бь р услови х Е* Ее я и, конечны? Гыть пустым. Прн каких е0.2.7. Постройте полные и (а) (а Ь)', ые порядки на следующих языках: (б) а*Ь"с", (в) (Гс ! иГ Е 1а, Ь)" и ч испо символов а в иГ равно числу сим- ( фф 0.2.8. Какие из сле ю и суффикспым) свойством: ду щих языков обладают префиксным Г) Об ати 1 Обратите внимание, что (О!2)е ие то же самое, что (0,1,2!Г'. ель некотоиые пОнятия мАтамАтичаскои логики (а) 8 (б) (е), (в) (а"Ь"( и Р: 1) (г) (.*, если Е обладает префиксным свойством, (д) (Го(иГЕ(!а, Ь)' и число символов а в Ги равно числу сим- волов Ь).

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

Формальную математическую систему можно охарактеризо- вать с помощью следующих основных компонент: (!) основные символы, (2) правила образования, (3) аксиомы, (4) правила вывода. Множество основных символов содержит символы для обозначения констант, операторов и т. д. В соответствии с правилами обра- зования из этих основных символов строятся утверждения. Затем определяются примитивные утверждения, справедливость кото- рых принимается без доказательства.

Зти утверждения назы- ваются аксио,иами системы. Дачее задаются правила, посредсчвоиГ которых из справед- ливых утверждений можно выводить новые справедливые утвер- ждения. Такие правила называются правилами вывода. Если трсбуется доказать, что некоторое утверждение истинно в некоторой формальной системе, то доказательством этого утверждения будет такая последовательность утверждений, что (!) каждое утверждение либо является аксиомой, либо его можно получить из одного или более предыдущих утверждений с помощью правила вывода; 0.3.3. Логические связки Р— ~0 Л Л И И И Л И И И Л Л Л Л Л И Л И И И И И Л И 2 А. Алл, Дж, Ульяал, т. 1 33 32 ГЛ, О, ПРЕДВАРИТЕЛЬНЫЕ МАТЕМАТИЧЕСКИЕ СВЕДЕНИЯ (2) последнее утверждение последовательности является тем утверждением, которое надо доказать.

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

Поэтому математики постоянно пользуются различными сокращениями, уменьшающими длину доказательства. Утвсрждения, ранее доказанные как теоремы, можно вставлять в доказательства. Можно опускать некоторые утверждения, когда (как мы надеемся) ясно, что происходит.

Зти приемы практикуются в сущности везде, и данная книга не составляет искл!Очення. Известно, что невозможно дать универсальный метод доказательства теорем. Однако в последующих разделах мы упомянем о некоторых широко распространенных частных приемах. 0.3.2. Доказательство иидукцией Допустим, мы хотим доказать, что утверждение 5(п) о натуральном числе и истинно для всех чисел из множества )ч'.

Если Л! конечно, чо один из методов доказательства заключается в проверке того, что 5 (и) истинно для каждого значения п из Л'. Зтот метод иногда называют доказательством исчерпыванием. Если Л! †бесконечн подмножество натуральных чисел, то можно применить простую математическую индукцию. Пусть и,— наименьшее число из Ж. Чтобы доказать, что 5(п) истинно для всех пЕ й!, надо (!) показать, что 5(п,) истинно (это называется базисом индукции), (2) предполагая, что 5 (т) истинно для всех т < и, принадлежащих !ч', показать, что 5(п) тоже истинно (это называется и!агам индукции). Пример 0.14.

Пусть 5(п) — утверждение !+3+5+... +2п — 1=п' Мы хотим показать, что 5 (п) истинно для всех положительных целых чисел. Таким образом, (ч =(1, 2, 3, ...). С.З. НЕКОТОРЫЕ ПОПЯТИЯ МАТЕМАТИЧЕСКОЙ ЛОГИКИ Базис. Для п-1 имеем 1=1'. Шаг индукции. Предполагая, что 5 (1), ..., 5 (и) истинны (в частности, что 5 (п) истинно), имеем 1+ 3+ 5+... + (2п — 1) + (2 (и + 1) — 1) = и'+ 2п + 1 ==- (и + 1)л так что 5(а+1) тоже истинно. О!сюда заключаем, что 5(п) истинно для всех положительных целых чисел. Д Примеры доказательств индукцией, применяемых не к натуральным числам, читатель найдет в равд. 0.5.5. Утверждения (теоремы) часто формулируются в виде „Р тогда и только тогда, когда !г" или „Р вЂ необходим и достаточное условие для !г'", причем Р и !г сами являются утверждениями. Термины если, тогда, только тогда, необходимо, достаточно и др. имеют точный смысл в логике. Логическая связка — это символ, с помощью которого можно образовать утверждение нз более простых утверждений.

Примеры логических связок: или, и, не, влечет, причем не — унарная связка (т. е. присоединяемая к одному' утверждению), а остальные — бинарные связки (т. е. связывающие два утверждения). Если Р и !г — утверждения, то Р и !',!, Р или !г, ие Р и Р влечет 9--тоже утверждения. Символ Р! обозначает связку и, !/ — связку или, — пе и — — влечет.

Существуют точные правила, определяющие истинность или ложность утверждения, содержащего логические связки . Например, утверждение Р и !г истинно только тогда, когда истинны оба утверждения Р н 9. Свойства логических связок можно резюмировать в виде таблицы, называемой таблицой истинности, в которой даны значения составных утверждений в зависимости от значений их компонент. На рис. 0.5 приведена таблица истинности для логических связок и, или, не и влечет. Рис. О.б.