Математическая логика и теория алгоритмов. Галуев Г.А. - 43 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 43 из 64
© 2003 Галуев Геннадий Анатольевич
Рассмотрим теперь различные уточненные формулировки понятия алгоритма и пока-
жем взаимосвязь между ними.
Алгоритмические системы.
Введем ряд понятий и определений. Пусть имеем непустое множество А, кото-
рое назовем алфавитом или словарем, а его элементы – символами или буквами. На-
пример, алфавит А={+, ?, r, a, b, z}. Он содержит шесть букв.
Произвольную конечную последовательность букв будем называть словом или
цепочкой в этом алфавите. Слово считается ориентированным слева - направо. На-
пример, последовательность А
=+a+b? является словом, а последовательность B=z+a-
b? не является словом (так как знак '' - '' отсутствует в А) в алфавите А . Слово, не
содержащее никаких букв называется пустым и обозначается Е.
Число букв, входящих в слово, называется его длиной, длина А=5 и обознача-
ется
A . Ясно, что E =0.
Пусть А* - множество всех слов в алфавите А, и пусть А, В
∈
А*. Упорядоченной
паре <А,В> поставим в соответствие слово С, полученное приписыванием к слову А
слова В. Говорят, что слово С получено конкатенацией(умножением) А и В и записы-
вают С=АВ. Таким образом, конкатенация это с одной стороны операция приписыва-
ния А к В, а с другой – результат этого
приписывания, то есть С=АВ.
Пусть А=cacb и B=abb, тогда С=cacbabb=АВ, а ВА=abbcacb. Длина конкатена-
ции С равна сумме образующих ее слов.
Ясно, что конкатенация является всюду определенной и ассоциативной, но не
коммуникативной операцией, то есть для любых А, В, С
∈
A
* имеет место:
А(ВС)=(АВ)С=АВС и АВ
≠ ВА. Кроме того, АЕ=ЕА=А, где Е играет роль единич-
ного элемента. Поэтому множество
A
* по операции конкатенации является свобод-
ной полугруппой над
A . Причем элементы A являются образующими этой полугруп-
пы.
Пусть P, Q, A, X, Y различные слова в алфавите
A и пусть А=XPY. Тогда слова
типа X; P; Y называются вхождениями в слово А. Слова типа X; XP; PY – называются
подсловами слова А.
Пусть имеется подстановка вхождения слова Q место слова Р и наоборот, то
есть P~Q. Тогда слову А можно поставить в соответствие слово В и наоборот, из сло-
ва В получить слово А.
Например, Р=
⎣⎦
apa Q=
⎣⎦
ло . Тогда слову А= п
⎣
⎦
ара д соответствует слово
В=п
⎣⎦
ло д.
То есть имеются два вхождения P и Q в слова А и В. такие, что вместо Р в слово
А можно подставить Q и получить слово В и наоборот.
Такие соотношения называются соотношениями ТУЭ (по имени норвежского ма-
тематики Акселя Туэ).
Они приводят (соотношения ТУЭ) к одному из вариантов ассоциативного исчис-
ления.
Два
слова А и В называются смежными, если одно из них получено из другого
однократным применением соотношений ТУЭ. В общем случае, можно допустить не-
сколько последовательных применений соотношений ТУЭ. Пусть А – некоторый алфа-
вит и R:
11
~ QP , …,
nn
QP ~ - система соотношений ТУЭ.
Говорят, что слово
0
B соотносимо со словом
p
B , если существует последовательность
слов
p
BB ,...,
0
, таких, что
i
B смежно с
1−i
B для i= 1,…,p.
Будем считать, что любое слово соотносимо с самим собой. Тогда соотносимость будет
рефлексивным, симметричным и транзитивным отношением, то есть отношением эк-
вивалентности. Это позволяет соотносимые слова называть эквивалентными и обо-

Страницы