Асоціативне числення
Асоціативне числення — важлива частина теорії алгоритмів, яка допомагає описувати алгоритми прикладних задач. Асоціативним численням називається сукупність всіх слів в даному абстрактному алфавіті разом з деякою скінченною системою допустимих підстановок. Асоціативне числення задається алфавітом і системою допустимих підстановок.
Асоціативне числення слів
В асоціативному численні слів вводяться допустимі операції підстановок без будь-яких обмежень на порядок їх застосування. Якщо U — деякий алфавіт, а A і B — слова в ньому, то неорієнтована підстановка позначається A ↔ B. Наприклад, підстановка ab ↔ bcb у двохелементному алфавіті U = {a, b} може бути застосована до слова abcbcbab в різному порядку, тобто можна в цьому слові виділяти (не обов'язково зліва) або слово ab, або слово bcb, тобто abcbcbab, або abcbcbab, або abcbcbab або abcbcbab.
Якщо слово A є результатом одного застосування допустимої підстановки до слова B, то очевидно, що слово B також є результатом застосування цієї ж підстановки до слова A; такі два слова називаються суміжними словами. Послідовність слів A1, A2,…, An, в якій два сусідні слова є суміжними, називається дедуктивним ланцюгом, який з'єднує слова A1 і An. Два слова A і B називаються еквівалентними (позначається A B), якщо існує дедуктивний ланцюг, який з'єднує ці слова. Ясно, що є відношення еквівалентності.
Проблема еквівалентності слів
Проблема еквівалентності слів полягає в тому, що для довільних двох слів даного асоціативного числення необхідно визначити чи еквівалентні вони, чи ні. Ця проблема має важливе теоретичне і практичне значення в математиці.
Індекс входження літери, індекс слова
Індексом входження літери «a» в слово X називається число всіх входжень літери «c», які зустрічаються правіше літери «a». Індексом слова X називається сума індексів всіх входжень літери «a». Наприклад, в слові «accac» перша зліва літера «a» має індекс 3, друга — 1, індекс слова — 4.
Приклад
Асоціативне числення задається алфавітом {a, b,c} і системою допустимих підстановок:
ac ↔ ca
bc ↔ cbРозглянемо нормальний алгоритм:
ba → ab
ba → abРезультатом застосування цього нормального алгоритму до довільного слова X в алфавіті {a, b,c} є слово, у якого є всі літери слова X, але вони упорядковані так, що спочатку йдуть всі літери «a», за ними — всі літери «b», і потім «c». Наприклад:
Алгоритм A2 перетворює еквівалентні слова в даному асоціативному численні в рівні слова.
Джерела та література
- Конспект лекцій з математичної логіки та теорії алгоритмів / В. С. Трохименко — Вінниця: 2007. — 86с.
- Основания теории множеств / Френкель А. А., Бар-Хиллел И. — М.: Мир, 1966. — 557с.
- Введение в математическую логику, т.1 / Черч А. — М.: Издательство иностранной литературы, 1960. — 478.