Понятие ассоциативного исчисления

Пусть нам задан алфавит – совокупность (конечная) попарно – различных символов А = {a₁, a₂, a₃, …, a_n, …}. Символы a_i, составляющие алфавит, называются буквами.

Определение 2.1. Словом в алфавите А называется любая конечная последовательность букв, записанных подряд слева направо.

Примеры: а) Записи любого натурального числа в десятичном счислении 21, 3, 321, 1101 есть примеры слов в алфавите А {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

б) Пусть А = {0, 1}. Тогда любое двоичное число 000, 001, 0010, 1101, 1111, … задаёт слово в этом алфавите.

в) Если алфавит А = {а, b, с}, то тогда словами будут следующие наборы: аbcc, cbbabbc, b, bbb, (знак - означает пустое слова, не содержащие ни одной буквы).

Определение 2.2. Количество букв в слове называется длиной слова. Длина пустого слова равна нулю.

Определение 2.3. Два слова P и Q в одном и том же алфавите А называется равными (обозначается P = Q), если они одинаково записаны т.е. на соответствующих позициях стоят одинаковые буквы.

Определение 2.4. Композицией двух слов P и Q в одном алфавите А называется новое слово в том же алфавите, которое получается приписываем к слову P справа слова Q и обозначается P Q (или PQ).

Например, если P = 2131 и Q = 965, то QP = 9652131, PQ=2131965.

Очевидно операция композиции слов не коммутативно (PQ PQ), но ассоциативна т. е. если даны три слова P, Q и R в одном алфавите А, то (P Q) R = P (Q R) = PQR.

Например, P = 231, Q = 453, R = 19, тогда (P Q) R = (231 453) 19 = 231453 19 = 23145319; P (Q R) = 231 (45319)= 23145319 = 23145319.

В силу ассоциативности операции композиции слов вводимое нами счисление называется ассоциативным.

Определение 2.5. Пусть нам даны два слова P и Q в алфавите А. Говорят, что слово Р входит в слово Q (или слово Q содержит слово Р), если слово Q представимо в виде композиции Q = RPS, где R или S – быть может пустые слова.

Например, слово 12 входит в слово 241291247, причем 2 раза.

Очевидно, что каждое слово содержит себя и пустое слово входит в любое другое слово.

Если слово Р входит в слово Q несколько раз, то тогда говорят о первом, втором и т. д. вхождениях, обозревая слово Q слева направо.

Определение 2.6. Говорят, что два слова P и Q в одном и том же алфавите А, соединённые между собой чёрточкой задает неориентированную подстановку P – Q. Если же слова P и Q соединены стрелочкой P Q, то подстановка называется ориентированной.

слово R содержит слово Р из подстановки P – Q. Заменим какое – то вхождение слова Р в слово R на слово Q. При этом получится новое слово R1. При этом говорят, что слово R1 получено из слова R с помощью подстановки P – Q за 1 шаг.

В случае, когда подстановка неориентированная, разрешается заменять как вхождение Р на Q, так и вхождение Q на P. Если же подстановка P Q – ориентированная, то замена разрешается лишь в указанном стрелкой направлении.

Например, применяя подстановку ab – аbb к слову R = bаbbа слева направо, получим слово R1= bаbbbа, а применяя ту же подстановку вправо налево – получим слово R2= bаbа.

Может оказаться, что подстановка P – Q не применима к слову R, т. к. R не содержит ни P, ни Q. Например, подстановка аb – аbb к слову S = асbbсаа применима.

Если рассматривать не одну, а несколько подстановок в одном алфавите
P1– Q1, P2– Q2, P3 – Q3, …, Ps– Qs, ()

и применять эти подстановки к слову R и к получаемым при этом словам R1, R2, … до тех пор, пока это возможно получится некоторое множество слов, которое называется множеством, порожденным из слово R с помощью системы подстановок ().

Например, если иметь подстановки 1) аа с, 2) bb а, 3) сс , то, применяя их к слову R = аbb, получится следующее множество: {abbc, aac, cc, }.

Определение 2.7. Совокупность всех слов в алфавите А вместе с какой-нибудь конечной системой подстановок называется ассоциативным счислением.

Из определения 2.7 следует. Что для задания конкретного счисления достаточно указать алфавит и конечную последовательность подстановок в этом алфавите: например, алфавит В = {а, b, , 0} и в нем система из четырёх подстановок 1 ) аb b ; 2) а 0 ; 3) 0 0; 4) 0 задаёт ассоциативное счисление.

Определение 2.8. Два слова P и Q в некотором ассоциативном счислении называются смежными, если одно из них получается из другого за одно применение какой – либо подстановки данного счисления.

Так в предыдущем примере слова аа 0b а и ааb а смежные, т. к. второе слово получатся из первого с помощью подстановки 0 0. В то же время слова ab0ba и а 0b не являются смежными.

Определение 2.9. Два слова P и Q в данном ассоциативном счислении называются эквивалентными (обозначается P~Q), если существует такая конечная цепочка слов P, P1, P2, …, Ps, Q, которая начинается со слова Р, завершается словом Q и которой пары (Р, Р1), (Р1, Р2), (Р2, Р3), …, (Рs, Q) смежные.

Нетрудно понять, что

а) каждое слово эквивалентно самому себе (рефлексивность);

b) если P~R и R~Q, то P~Q (транзитивность);

с) если подстановки счисления не ориентированы, то из P~Q следует, что Q~P (симметричность).

Из перечисленных свойств следует, что в ассоциативных счислениях с системой неориентированных подстановок отношение эквивалентности ~ разбивает множество слов в алфавите счисления на классы эквивалентности: произвольные два слова R1 и R2 будут в одном классе тогда, когда R1~ R2. При этом количество различных классов для одних ассоциативных счислений может быть конечным, для других бесконечным.