Лекции 19. Алгоритмы Маркова
Ассоциативные исчисления. Пусть имеется алфавит (конечный набор различных символов). Составляющие его символы будем называть буквами. Любая конечная последовательность букв алфавита (линейный их ряд) называется словом в этом алфавите. Рассмотрим два слова N и М в некотором алфавите А. Если N является частью М, то говорят, что N входит в М. Зададим в некотором алфавите конечную систему подстановок N - М, S - Т,..., где N, М, S, Т,... - слова в этом алфавите. Любую подстановку N-M можно применить к некоторому слову К следующим способом: если в К имеется одно или несколько вхождений слова N, то любое из них может быть заменено словом М, и, наоборот, если имеется вхождение М, то его можно заменить словом N. Пример. Пусть в алфавите А = {а, b, с} имеются слова N = ab, М = bcb, К = abcbcbab, Заменив в слове К слово N на М, получим bcbcbcbab или abcbcbbcb, и, наоборот, заменив М на N, получим aabcbab или аbсаbаb. Подстановка ab - bcb недопустима к слову bacb, так как ни ab, ни bcb не входит в это слово. К полученным с помощью допустимых подстановок словам можно снова применить допустимые подстановки и т.д. Совокупность всех слов в данном алфавите вместе с системой допустимых подстановок называют ассоциативным исчислением. Чтобы задать ассоциативное исчисление, достаточно задать алфавит и систему подстановок. Слова P1 и Р2 в некотором ассоциативном исчислении называются смежными, если одно из них может быть преобразовано в другое однократным применением допустимой подстановки. Последовательность слов Р, P1, Р2, ..., М называется дедуктивной цепочкой, ведущей от слова Р к слову М, если каждое из двух рядом стоящих слов этой цепочки - смежное. Если можно построить цепочку, ведущую от слова R к слову S, то в силу симметричности подстановок можно построить и цепочку, ведущую от S к R. Слова R и S будут эквивалентными в данном ассоциативном исчислении (R~S). Пример. Алфавит {а, b, с, d, е}. Подстановки: ас – сa; abac - abace ad - da; eca - ae bc - cb; eda - be bd - db; edb - be Слова abcde и acbde - смежные (подстановка bc - cb). Слова abcde и cadbe -эквивалентны.