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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 46 из 64
© 2003 Галуев Геннадий Анатольевич
Например: Пусть имеется нормальная система с алфавитом А={a,b}, аксио-
мой bba и подстановками 1)aP→Pbba; 2)bP→Paba, где P - некоторое слово в алфавите
А.
Ориентированный граф, задающий множество всех выводимых формул имеет вид
Эта нормальная система является моногенной.
Например: Пусть имеется полутуэвская система с алфавитом А={a,bc}, B={s},
где s – аксиома, и подстановками : 1) s→as; 2) s→sb; 3) s→asb; 4) s→c.
Если изобразить граф выводимых в данной системе формул, то можно убедиться,
что формула acb является неоднозначной, так как для нее существует три разных вы-
вода.
1.S
⎯→⎯
1
as ⎯→⎯
2
asb ⎯→⎯
4
acb
2.S
⎯→⎯
2
sb ⎯→⎯
1
asb ⎯→⎯
4
acb
3.S
⎯→⎯
3
asb ⎯→⎯
4
acb
Поэтому эта полутуэвская система является неоднозначной.
Лекция 9.
Соответствие между полутуэвской и нормальной системой.
Пусть задана полутуэвская система П, состоящая из алфавита А={a,b,c}, слова
с
∈А – аксиома и подстановок QPBQPA
ii
→ ( mi
≤
≤
1 ). Добавим в алфавит А буквы со
штрихами и получим алфавит В={a,b,c,a',b',с'}. построим нормальную систему N,
включающую алфавит В, ту же аксиому
C , сопряженную с С и следующие подстанов-
ки:
1) aP→Pa', bP→Pb', cP→Pc' ;
2) a'P=Pa, b'P→Pb, c'P→Pc;
3)
ii
PBPA → ' mi
≤
≤1
Заметим, что подстановки типов 1) и 2) позволяют переставлять некоторую бу-
кву из начала слова в его конец, меняя при этом её ''штриховость'' на обратную.
Например, применяя к слову baab подстановки 1) и 2) можно получить циклический
вывод:
baab
⎯→⎯
1
aabb` ⎯→⎯
1
abb`a` ⎯→⎯
1
bb`a`a` ⎯→⎯
1
b`a`a`b` ⎯→⎯
2
a`a`b`b ⎯→⎯
2
a`b`ba
⎯→⎯
2
b`baa ⎯→⎯
2
baab.
Все слова в этой цепочке называются сопряженными. Каждая совокупность со-
пряженных слов образует класс эквивалентности. Заметим, что среди всех слов, со-
пряженных со словом А, есть и А'. Поэтому подстановки 1) и 2) позволяют за не-
сколько шагов переставлять слова из начала в конец.
Все слова, имеющие форму PQ' или P'Q; где P,Q
∈
A*, сопряженные со словом
из А* и только с ними, называются регулярными
.
В классе эквивалентности, рассмотренном выше, не существует регулярных слов. А
в классе эквивалентности:
abba
⎯→⎯
1
bbaa` ⎯→⎯
1
baa`b` ⎯→⎯
1
aa`b`b` ⎯→⎯
1
a`b`b`a` ⎯→⎯
2
b`b`a`a ⎯→⎯
2
b`a`ab
⎯→⎯
2
a`abb ⎯→⎯
2
abba

Страницы