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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 45 из 64
© 2003 Галуев Геннадий Анатольевич
3. Конечное множество правил вывода, задаваемых ориентированными подста-
новками.
В простейшем случае ориентированная подстановка имеет вид: А→В, где А и В
слова в алфавите A
U B. подстановка такого вида является бесконтекстной, называет-
ся полутуэвской и означает, что слово А заменяется словом В. ясно, что обратная
подстановка В→А также является полутуэвской. Если имеются одновременно прямая
А→В и обратная В→А подстановки, то их можно заменить одной неориентированной
подстановкой, которая обозначается А~В и называется туэвской.
При наличии кон-
текста полутуэвская подстановка имеет вид PAQ→PBQ, где P и Q некоторые(возможно
и пустые) в том же алфавите, что А и В.
Ориентированная подстановка AP→PB называется нормальной, обратная к ней
подстановка PB→AP называется антинормальной. Совокупность нормальной и анти-
нормальной подстановок, то есть неориентированная подстановка вида AP~PB назы-
вается постовской.
Таким образом
, в зависимости от используемой подстановки, можно рассматривать
следующие 4 вида комбинаторных систем: полутуэвская, туэвская, нормальная и по-
стовская.
Например: пусть задана полутуэвская система, в которой А={a,b} – основной
алфавит, B={s} - вспомогательный алфавит, состоящий из одной буквы – аксиомы s,
и три подстановки
1) s→ab 2) s→asb 3)s→bsa.
Тогда множество всех формул, выводимых в этой системе из
аксиомы s с помо-
щью заданных подстановок можно представить в виде бесконечного ориентированно-
го графа, каждая вершина которого помечена некоторым словом из алфавита A
U B.
Дуги (ребра) графа помечаются номером подстановки. Фрагмент такого графа пока-
зан ниже
В любую вершину графа, полученную формулой из вершины S ведет один путь.
Он (этот путь или эта ветвь графа) как раз и соответствует выводу этой формулы.
Например, вывод формулы aaabbb из S имеет вид
S
⎯→⎯
2
asb ⎯→⎯
2
aasbb ⎯→⎯
1
aaabbb.
Для вершин графа помеченных только буквами алфавита А={a,b}. Вывод фор-
мулы в данной комбинаторной системе продолжен быть не может (вершины такие за-
штрихованы).
Комбинаторная система называется моногенной (однозначной), если к любой ее
формулы может быть применено не более одной подстановки.
Комбинаторная система называется неоднозначной, если в ней имеется формула, для
которой существует по крайней мере два различных вывода.
bsa
absab
asb
ab
aasbb
aab
aaasbbb
aaabbb
S
3
2
1
1
1
2
2
3

Страницы