Приклад 3

Приклад 2

Приклад 1

Нехай для слів в алфавіті V={a,b,c,d} задані наступні підстановки Маркова:

а)abг) acж)к)

б)д)з)л)

в)е)і)

Застосувати кожну з них до слова abcddacba.

Розв’язання:

Для застосування підстановки Маркова Р до деякого слова, потрібно знайти в слові перше входження підслова Р і замінити його словом Q. В даному випадку для підстановок а)–і) підслово Р входить в дане слово тільки один раз. Це входження легко замінити на підслово Q.Наприклад, для підстановки б) отримаємо. Але для підстановки г) перше входження слова в даному випадку є, а не. Тому отримаємо. Підстановка з) дасть В підстановках к) і л) кожне з перших слів входить в дане слово неодноразово, важливіше є перше входження. Для цих підстановок отримаємо.

НОРМАЛЬНІ АЛГОРИТМИ ТА ЇХ ЗАСТОСУВАННЯ

Впорядкована скінченна сукупність підстановок Маркова в алфавіті

V:

визначає наступне правило побудови послідовності слів в алфавіті V, виходячи із даного слова W в цьому алфавіті, що має назву нормального алгоритму (Маркова) в алфавіті V. Крапка в дужках означає, що кожна підстановка може бути завершальною. Якщо ж алгоритм заданий в деякому розширенні алфавіту V, то кажуть, що він є нормальний алгоритм над V.

Нормальний алгоритм в алфавіті V={a,b,1} задається схемою. Застосуйте його до слова

Розв’язання:

Робота алгоритму завершена.

НОРМАЛЬНО ОБЧИСЛЮВАЛЬНІ ФУНКЦІЇ

Будемо розглядати числові функції, тобто функції задані на множині натуральних чисел. Натуральні числа кодуються словами в алфавіті V={1}, так, що розглядаються функції, задані словами над цим алфавітом. При цьому, функція f, задана на деякій множині слів алфавіту V, є нормально обчислювальною, якщо знайдеться таке розширення в даного алфавіту) і такий нормальний алгоритм в В, що кожне слово Р (в алфавіті V) з області визначення функції f цей алгоритм перетворює в слово f (Р) (в алфавіті V).

Також розглянемо функції для обчислення яких будуються нормальні алгоритми в розширених алфавітах. Алфавіт V={0,1,….9}будемо називати основним.

В алфавіті В=, що є розширенням алфавіту А, розглянемо нормальний алгоритм, що задається схемою (читається по стовпцях):

Застосувавши його до слова 3000, показати, що він обчислює функцію f (х) = х-1

Розв’язання:

Алгоритм працює наступним чином: спочатку застосовується остання підстановка: 3000. Потім підстановки з 2-го стовпчика, поки а не займе крайнє праве положення: Тепер застосуємо підстановку з третього стовпця: Використаємо з першого стовпця: 3000. Знову застосовуємо підстановку до тих пір поки, лівіше букви b не отримується цифра відмінна від 0:. Тепер завершальна підстановка отримаємо

Запитання для самоперевірки.

1. Що таке ланцюжок?

2. Як називається операція над ланцюжками?

3. Що таке формальна породжувальна граматика?

4. Як будується дерево виведення?

5. Як обчислюються функції за допомогою нормального алгоритму?

Література

1. (Б2), с.351-356,

2. (Б8), с.389-396.

Дата добавления: 2014-01-07