Теория языков программирования методов трансляции (стр. 3 )

Рис. 1.6. Частичный порядок

Определение.

Рефлексивным частичным порядком называется отношение R, если

1)  R – транзитивно;

2)  R – рефлексивно;

3)  если aRb, то a=b.

Последнее свойство называется антисимметричностью.

Каждый частичный порядок можно графически представить в виде ориентированного ациклического графа.

Линейный порядок R на множестве А – это такой частичный порядок, что, если а и bÎА, то либо aRb, либо bRa, либо a=b. Удобно это понять из следующего.

Пусть А представлено в виде последовательности а1, а2,…,an, для которых тогда и только тогда, когда i<j.

Аналогично определяется рефлексивный линейный порядок.

Из традиционных систем отношение < (меньше) на множестве неотрицательных целых чисел – это линейный порядок, отношение £ - рефлексивный линейный порядок.

Отображение

Отображением (функцией преобразования) М множества А во множество В называют такое отношение из А в В, что, если (a, b) и (а, с) принадлежат М, то b=c. Если (a, b)ÎM, то обычно пишут М(а)=b.

М(а) определено, если существует такое bÌ B, что (a, b)ÎM.

Если М(а) определено для всех аÎА, то М всюду определено.

Если М(а) определено не для всех аÎА, то М – частичное отображение

Если отображение М:А®В таково, что для каждого bÎB существует не более одного аÎА такого, что М(а)=b, то М называется инъективным (взаимно однозначным) отображением.

Если М всюду определено на А и для каждого bÎB существует точно одно аÎА такое, что М(а)=b, то М называют биективным отображением.

Обратное отображение обозначается .

Определение.

Два множества А и В называются равномощными, если существует биективное отображение А в В.

Определения:

1)  множество S конечно, если оно равномощно множеству {1, 2,…, n} для некоторого целого n;

2)  множество S бесконечно, если оно равномощно некоторому своему собственному подмножеству;

3)  множество S счетное, если оно равномощно множеству положительных чисел.

1.3.  Множества цепочек

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

Символ – (синонимы: буква, знак) элемент алфавита.

Пример:

01011 – цепочка в бинарном алфавите {0, 1}.

Особый вид цепочки – пустая цепочка, обозначается e. Пустая цепочка не содержит символов.

Соглашение.

·  Прописные буквы греческого алфавита – алфавиты.

·  a, b, c и d – отдельные символы.

·  t, u, v, w, x, y и z – цепочка символов.

Если цепочку из i символов обозначить a®, тогда a0=e – пустая цепочка.

Определение:

Цепочки в алфавите S определяются следующим образом:

1)  е – цепочка в S;

2)  если x цепочка в S и аÎS, то xa – цепочка в S;

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

Операции над цепочками

Пусть x, y – цепочки.

·  Цепочка xy – называется сцепленной (конкатенацией). Например, x=ab; y=cd; xy=abcd. Для любой цепочки x xе=еx=x.

·  Обращением цепочки x называется цепочка x, записанная в обратном порядке: , ,.

·  Пусть x, y, z – цепочки в некотором алфавите S, тогда:

x – префикс цепочки xy;

y – суффикс цепочки xy;

y – называется подцепочкой цепочки xyz.

Префикс и суффикс цепочки являются ее подцепочками.

Если x¹y, x – префикс (суффикс) цепочки y, то x - собственный префикс (суффикс) цепочки y.

Длина цепочки – это число символов в ней. Если , то длина цепочки n. Длину цепочки обозначают |x|, например |abc|=3; |e|=0.

1.4.  Языки

Языком в алфавите S называют множество цепочек в S.

Определение.

Через S* обозначается множество, содержащее все цепочки в алфавите, включая е.

Например. S - бинарный алфавит {0,1}, тогда S*={e, 0, 1, 00, 01, 10, 11, 000, …,}.

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

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

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

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

Определение.

Пусть L1 язык в S1., L2 язык в S2. Тогда язык L1L2 называется конкатенацией языков L1 и L2 - это язык . Итерация языка L обозначается L*, определяется:

1)  L0={e};

2)  для n³1;

3)  .

Позитивная итерация языка L обозначается L+ - это язык , т. е.

Определение.

Пусть S1 и S2 - алфавиты. Гомоморфизмом называется любое отображение h: S1 ® S*2.

Область гомоморфизма можно расширить до полагая h(e)=e и h(xa)=h(x)h(a) для всех xÎ, и аÎ.

Пример.

Если мы хотим заменить каждое вхождение в цепочку символа 0 на а, а каждое вхождение символа 1 на bb, то можно определить гомоморфизм h так: h(0)=a, h(1)=bb. Если , то .

Определение.

Если h: S1 ® , то отношение h-1: ® P() называется обращением гомоморфизма.

Если yÎ, то h-1(y) – это множество цепочек в алфавите S1, т. е. . Если L – язык в алфавите S2, то - язык в алфавите состоящий из тех же цепочек, которые h отображает в цепочки из L. Формально

Пример.

h – гомоморфизм h(0)=a и h(1)=а, тогда

1.5.  Алгоритмы

Алгоритм - центральное понятие в компиляции и программировании, поэтому важно его формальное определение.

Частичные алгоритмы

Неформальное определение.

Частичный алгоритм состоит из конечного числа команд, каждая из которых может выполняться механически за фиксированное время и с фиксированными затратами.

Для того чтобы быть точным, необходимо определить термин «команда». Кроме того, частичный алгоритм имеет любое число входов и выходов. Эти переменные тоже требуют определения.

Пример.

Алгоритм Евклида (наибольший общий делитель)

Вход : p и q положительные числа

Выход: g – наибольший общий делитель p и q

Метод.

Шаг 1. Найти r - остаток от деления p и q.

Шаг 2. Если r=0, положить g=q и остановиться. В противном случае положить p=q, затем q=r и перейти к шагу 1.