ВУЗ:
Составители:
Рис. 1.1
В любую вершину графа, помеченную некоторой формулой, из
вершины s ведет один путь. Он как раз и соответствует выводу этой
формулы. Например, выводы формул вава и вваsваа имеют вид:
вававsаs
13
→→
;
вваsвааввsаавsаs
233
→→→
.
***, помеченных только буквами алфавита А, вывод формул в этой
комбинаторной системе продолжен быть не может.
Комбинаторная система называется моногенной (однозначной), если
каждой ее формуле может быть применено не более одной подстановки.
Комбинаторная система называется неоднозначной, если в ней имеется
формула, для которой существует по крайней мере два различных вывода.
Пример 1.2. Пусть имеется нормальная система с элементом
},{ ваА
=
,
аксиомой вва и подстановками 1)
PвввaP → , 2) РававР → , где Р - некоторое
слово в алфавите А.
Ориентированный граф, задающий множество всех выводимых
формул, показан на рис. 1.2
Рис. 1.2
Это нормальная система является моногенной.
Пример 1.3. Пусть имеется полутуэвская система с алфавитами
},,{ сваА = , }{sВ = , аксиомой s и подстановками: 1) ass → , 2) sвs → , 3) asвs → ,
4)
cs →
.
s
вsа
ав
(1)
(2)
(3)
аsв
аавв
(1)
(2)
(3)
ааsвв
аааввв
аааsввв
аавsавв
(1)
(2)
(3)
(1)
(2)
(3)
ававва аваsвва
аввsава
авsва
(1)
(2)
вава
ваsва
ваавва вааsвва
вавsава
вваваа
вваsваа
вввsааа
ввsаа
(1)
(2)
(3)
(3)
(2)
(1)
и так далее и так далее и так далее и так далее
(
2
)
вва
ваава
ааваава аваававвавва ваававвавва
(
2
)
(
1
)
(
1
)
и так далее.
Страницы
- « первая
- ‹ предыдущая
- …
- 15
- 16
- 17
- 18
- 19
- …
- следующая ›
- последняя »
