3. Алфавітні алгоритми.

Абстрактним алфавітом U називається скінченна сукупність різних знаків (символів), які називаються буквами цього алфавіту, при цьому природа букв немає значення.

Скінченна упорядкована послідовність букв алфавіту U називається словом в цьому алфавіті.

Наприклад, в алфавіті

U={a,b,c,d}

словами є послідовності

aa, dcb, ddccbb.

Слово, яке не містить жодної букви називається порожнім. Для позначення порожнього слова будемо використовувати символ L.

Два слова A і B називаються рівними, якщо вони складаються з однакових букв, які однаково розташовані.

Число букв, які входять до слова, називається його довжиною.

Якщо C=AB, то A початок слова C, а B його кінець.

Слово A входить в слово B ( ), якщо B=CAD, де слова C і D можуть бути порожніми.

Вважається, що порожнє слово в алфавіті U входить в будь-яке слово, між кожними двома сусідніми буквами, також перед першою і після останньої букв:

.

Алгоритмом в абстрактному алфавіті U називається скінченна сукупність допустимих операцій, яка конструктивно задає відповідність між словами в U.

Алгоритм А застосовний до слова X, якщо процес перетворень вхідного слова X алгоритмом А закінчується деяким словом Y:

A(X)=Y.

Сукупність всіх слів даного алфавіту, до яких застосовний алгоритм А, називається областю застосування алгоритму А.

Алгоритми A і B над алфавітом U називаються еквівалентними відносно U, якщо для будь-якого слова X в алфавіті U, до якого застосований алгоритм A, застосований також алгоритм B і результати їх дії збігаються, тобто

A(X)=B(X).

Універсальність алфавітного способу кодування інформації дає можливість побудувати досить загальну алгоритмічну систему, в якій конструктивними об’єктами (умовами задачі) є слова в абстрактному алфавіті. Такою алгоритмічною системою є теорія нормальних алгоритмів А.А. Маркова [1951 р.].

4. Означення нормального алгоритму.

Алгоритмічна система Маркова будується за визначеною вище загальною схемою побудови алгоритмічних систем.

Задається абстрактний алфавіт U. Вхідна інформація про задачу подається у вигляді слів в алфавіті U, тобто є конструктивними об’єктами.

Система допустимих операцій містить дві операції:

- підстановки (операція дії);

- входження (операція розпізнавання).

Операція підстановки записується у вигляді:

АВ,

де А і В - слова в даному алфавіті U, при цьому знак  не входить до алфавіту U.

Застосування операції підстановки АВ до даного слова Х полягає в тому, що перше зліва входження слова А в дане слово Х замінюється на слово B.

Якщо слово А входить у дане слово Х, то існує подання:

X=YAZ,

в якому Y - початок слова X, Z - кінець слова X. В результаті виконання підстановки АB над даним словом X дістаємо слово X₁ =YBZ.

Застосування операції підстановки АB до даного слова Х можливе лише за умови, якщо слово А входить у дане слово Х. У цьому випадку кажуть, що підстановка АB застосована до даного слова Х.

Якщо ліва частина підстановки АB, тобто слово А, не входить до слова Х, то підстановка АB незастосовна до даного слова Х.

Умову застосування підстановки АB до даного слова Х можна визначати значенням предиката “АХ”, який набуває значення “істина”(1), якщо А входить до Х, і значення “хиба” (0), якщо А не входить до Х.

Наприклад, нехай задане слово

Х=abba

і підстановка

abb.

Тоді, оскільки слово “a” входить в слово “abba”, то, застосувавши цю підстановку, одержимо слово

Y=bbbba.

До слова Y можна також застосувати задану підстановку, тоді результатом буде слово

Z=bbbbbb.

Частинними випадками підстановок є дві підстановки:

B,

A.

У підстановці B порожнє слово замінюється на слово B, а в підстановці А слово А замінюється на порожнє слово.

Приклад 1. Нехай задано алфавіт U={1,2,3,4,5} і слово Х=321445 в цьому алфавіті.

Треба знайти результат застосування підстановок 1 і 5.