Операції над словами.

Operations on words

Операции над словами

Будем обозначать заглавными буквами Р, Q, R, … из конца латинского алфавита знакосочетания в некотором фиксированном алфавите, а символы этого алфавита – строчными буквами а, б, с, … из начала латинского алфавита. Здесь и ниже слова “будем обозначать …посредством…”, где … обозначает…” и т.п. применительно к знакосочетаниям формального языка означают обращения к метаязыку. Введенные таким образом символы метаязыка могут использоваться вперемешку и знакосочетаниями формального языка, которые в подобных случаях использоваться автономно, т.е. как названия для самих себя, принадлежащие, конечно, метаязыку.

Применительно к обозначениям знакосочетаний формального языка в метаязыке будем использовать как символ метаязыка знак равенства =, чтобы выразить утверждение о тождественном совпадении знакосочетаний формального языка, чьи названия в метаязыке соединены этим знаком.

Для двух слов Р и Q будем обозначать РQ соединения (произведение, композицию, -- этих слов, т.е. слово получающееся, если к одной конечной последовательности символов – слову Р приписать другую конечную последовательность символов – слово Q, так что возникает новое слово, длина которого есть сумма длин перемноженных слов. Используя обычным образом скобки, чтобы указать последовательность построения композиции более чем двух слов, имеем---умножения слов

(P₁P₂) P₃ =P₁(P₂P₃),

что позволяет записывать композицию более чем двух слов без скобок, без потери однозначности результата, ибо всякая последовательность соединения составляющих слов в одно без изменения их порядка приводит к одному и тому же результату. В случае трех слов имеем два варианта построения композиции (Р₁Р₂)Р₃ и Р₁ (Р₂Р₃); сначала строится композиция знакосочетаний заключенных в скобки, а затем – композиция полученного таким образом знакосочетания со знакосочетанием не вошедшим в скобки; в любом случае имеем один и тот же результат Р₁Р₂Р₃.

Умножение слов обладает единицей, роль которой играет пустое слово, L т.е. пустая последовательность символов формального языка:

РL=L R = R

для любого слова Р.

Конечно коммутативность для умножения слов не имеет места: в общем случае

РQ ¹ QP,

хотя, когда одно из слов пустое или представляют собой произведение нескольких экземпляров другого, и только в этих случаях, произведение слов коммутативно.

Слово Q входит в слово Р и называется подсловом слова Р, называемого в таком случае подсловом для слова Q, если существуют такие слова U и V, возможно пустые,что P=VQU.Собственно подслово – это подслово, которое не пустое и не совпадает со всем словом. Может быть несколько разных вхождений подслова Q в слово Р (с разными V и U), причем в общем случае некоторые из вхождений могут перекрываться (часть символоа из одного вхождения может принадлежать к другому).

Результатом подстановки слова R вместо заданного вхождения слова Q в слово Р = VQU называют слово URV. В терминах этого действия могут быть описаны все словарные алгоритмы (теория марковских, А.А.Марков,1954, алгоритмов и тезис Черга, А.Church 19 )

Результат одновременной подстановки слова Q вместо всех вхождений символа, а в слово Р обозначают Р(а ¤ Q).Если

Р=U_o a U₁ a…aU_n,

где U_o,…Un – подслова не содержащие вхождений символа а, то

P(a/Q) = U_oQU₁₁ a…aU_n,

где U_o,…Un – подслова не содержащие вхождений символа а, то

P(a/Q) = U_oQU₁Q…QU_n.

Результат одновременной подстановки слов Q₁,…,Q_k вместо разных символов а₁…, а_к, соответственно, в слово Р обозначают P(a_1/Q₁,…a_k/Q_k).Подчеркнем, что результат одновременной подстановки вместо нескольких символов не совпадает в общем случае с результатом последовательных подстановок вместо этих символов если они входят и в подставляемые слова.