В качестве операций ассоциативного исчисления определяется система допустимых подстановок, с помощью которых одни слова преобразуются в другие. Подстановка вида L-M, где L и M — слова в том же алфавите, означает замену вхождения левой части правой, равно как и замену правой части левой. Иначе говоря, если в некотором слове R имеется одно или несколько вхождений слова L, то каждое из этих вхождений может заменяться словом M, и наоборот, если имеется вхождение слова М, то его можно заменить словом L. Например, подстановка ab-bcb применима четырьмя способами к слову abcbcbab. Замена каждого из двух вхождений bcb даст слова aabcbab и abcabab, а замена каждого из двух вхождений ab дает слова bcbcbcbsb, abcbcbbcb. В то же время к слову bacb эта подстановка не применима. Подстановка вида Р-∧ означает, что из преобразуемого слова выбрасывается вхождение слова Р,
- 624 -
а также что между двумя какими-либо буквами преобразуемого слова или впереди него, или за ним вставляется слово Р.
Итак, ассоциативное исчисление — это множество всех слов в некотором алфавите вместе с какой-нибудь конечной системой допустимых подстановок. Очевидно, чтобы задать ассоциативное исчисление, достаточно определить алфавит и систему допустимых подстановок (например, алфавит {a, b, c, d, e} и система подстановок ac-ca, ad-da, bc-cb, bd-db, abac-abacc, eca-ae, edb-be).
6. Эквивалентность слов. Два слова называются эквивалентными, если одно из них можно получить из другого последовательным применением допустимых подстановок. Так, в приведенном выше (5) исчислении эквивалентными являются, например, слова abcde cadedb, что видно из следующих последовательных преобразований: abcde, acbde, cabde, cadbe, cadedb. Последовательность слов R1, R2, ..., Rn, когда каждое следующее слово является результатом однократного применения допустимой подстановки к предыдущему слову, образует дедуктивную цепочку, причем соседние слова в этой цепочке называют смежными. Очевидно, любые два слова в дедуктивной цепочке являются эквивалентными.
Эквивалентность слов L и M обозначается L ~ M и обладает всеми свойствами отношения эквивалентности (рефлексивность, симметричность и транзитивность). Если L ~ M, то при наличии в каком-либо слове R вхождения L в результате подстановки L-M получается слово, эквивалентное R. Например, воспользовавшись эквивалентностью abcde~cadbe, из слова bbabcdec получаем эквивалентное ему слово bbcadbec.
В каждом ассоциативном исчислении возникает своя специальная проблема слов, заключающаяся в следующем: для любых двух слов в данном исчислении требуется узнать, эквивалентны они или нет. Решение этой проблемы аналогично поиску пути в лабиринте, площадки которого соответствуют смежным словам. Очевидно, эквивалентность двух слов означает, что соответствующие им площадки связаны некоторым путем, который представляет собой дедуктивную цепочку от одного слова к другому. Однако проблема слов является далеко идущим обобщением задачи поиска пути в конечном лабиринта. Так как в любом ассоциативном исчислении содержится бесконечное множество различных слов, то соответствующий лабиринт имеет бесконечное число площадок, и, следовательно, решение вопроса об эквивалентности любых двух слов сводится к поиску пути в бесконечном лабиринте.
С помощью алгоритма перебора решается ограниченная проблема слов: требуется установить, можно ли одно из заданных слов преобразовать в другое применением допустимых подстановок не более, чем k раз, где k — произвольное, но фиксированное число. Для этого достаточно построить все слова, смежные с одним из заданных слов,
- 625 -
затем для каждого из полученных слов построить все слова, смежные с ним и т.д. всего k раз. В результате получим список всех слов, которые можно получить из заданного с помощью допустимых подстановок, применяемых не более k раз. Если второе заданное слово окажется в этом списке, то ответ на поставленный вопрос будет положительным, а если его в списке нет, ответ отрицательный. Можно заметить, что ограниченная проблема слов соответствует ограничению лабиринта таким образом, что расстояние между рассматриваемыми площадками не превышает k коридоров.
Однако такой путь принципиально не пригоден для решения неограниченной проблемы слов. Поскольку длина дедуктивной цепочки, простирающейся между эквивалентными словами (если такая цепочка существует), может оказаться сколь угодно большой, то не существует никакой возможности указать такое конечное число k, которое гарантирует решение проблемы путем простого перебора. Поэтому для получения желаемых результатов необходимо применять другие идеи, основанные на анализе самого механизма преобразования слов посредством допустимых подстановок.