Зразок роботи
Теоретичні відомості
Алгоритмічна система, заснована на відповідності між словами в абстрактному алфавіті, включає об’єкти подвійної природи: елементарні оператори і елементарні розпізнавачі.
Елементарні оператори − алфавітні оператори за допомогою послідовного виконання яких реалізується будь-який алгоритм у даній алгоритмічній системі.
Елементарні розпізнавачі служать для розпізнавання присутності тих або інших властивостей інформації, яка переробляється алгоритмом, і для зміни, залежно від результатів розпізнавання, послідовності, в якій ідуть один за одним елементарні оператори.
У нормальних алгоритмах у вигляді елементарного оператора використовується оператор підстановки, а у вигляді елементарного розпізнавача − розпізнавач входження.
особливістю НАМ є те, що у них використовується лише одна елементарна дія - так звана підстановка, яка визначається наступним чином: оператором підстановки називається запис вигляду α→β (читається «α замінити на β»), де α і β − будь-які слова (можливо, і порожні). При цьому α називається лівою частиною оператора, а β - правою частиною.
Підстановка задається оператором підстановки і застосовується до деякого слова р. Суть операції зводиться до того, що у слові р шукається підслово, яке співпадає з лівою частиною даного оператора (тобто з β), і воно замінюється на праву частину оператора (на α). При цьому решта підслів слова р (зліва і праворуч від α) не змінюється. Отримане у результаті підстановки слово q називають результатом підстановки. Нормальним алгоритмом Маркова (НАМ) називається непорожній скінчений впорядкований набір операторів підстановки:
У цих операторах можуть використовуватися два види стрілок: звичайна стрілка (→) і стрілка «з хвостиком» ( ).
Індивідуальне завдання
Задати НАМ, який реалізує віднімання А − Б, де значеннями А і Б є натуральні числа, представлені рядками, що складаються з символів 1 (наприклад, для А= 4, Б = 3, А − Б = 1 слово “1111−111” повинне бути перероблене алгоритмом у слово “1”).
Перевірити роботу алгоритму для випадків:
а) А = 6, Б = 2;
б) А = 3, Б = 5.
Розвязок
а) А = 6 = 111111 , Б =2 = 11
А-Б = 111111-11=4(1111)
1) 1-1 → 111111-11
2) 1-1 → 11111-1
3) 1-1 → 1111
4) → Λ 1111
б) А =3=111, Б=5=11111
А-Б = 111-11111
У цьому прикладі алгоритм дещо ускладнюється , оскільки треба проаналізувати процес завершення, коли після дії підстановки ׀˗׀→˗ поточне слово буде починатися з підслова “˗׀”.
#include
Магістр