Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій, Детальна інформація

q0|( q1(L

q1|( q2(L

q2|( q2|R

q2(( q3(L

q3 a( q3 aL

q3|( q4aL

q4|( q4|L

q4(( q0(R

q1 a( q0 a

q2 a( q0 a

q0a( q0|R

Приклад 10. МТ, яка кожне слово х(Т* переводить в слово х#х

(тут #(T).

q0 t( q0 tR для всіх t(T

q0(( q1#L

q1 t( q1 tL для всіх t(T

q1(( q2(R

q2 t( qt (R для всіх t(T

qt p( qt pR для всіх t(T, p(T({#}

qt (( q't tL для всіх t(T

q't p( q't pL для всіх t(T, p(T({#}

q't (( q2tR для всіх t(T

q2#( q*#

3. НОРМАЛЬНІ АЛГОРИТМИ МАРКОВА

Пiд нормальним алгоритмом (скорочено НА) в алфавiтi T розумiють впорядковану послiдовнiсть продукцiй (правил) вигляду ((( або ((((, де (, ((T* та ( , ((T. Продукцiї вигляду (((( називають фiнальними.

Кожен НА в алфавiтi T задає деяке вербальне вiдображення T*\x2192T*. Слово, яке є результатом обробки слова x нормальним алгоритмом A, позначимо A(x). Обробка слова x нормальним алгоритмом A проводиться поетапно таким чином.

Покладемо x0=x i скажемо, що x0 отримане iз x пiсля 0 етапiв. Нехай слово xn отримане iз слова x пiсля n етапiв. Тодi (n+1)-й етап виконується так.

Шукаємо першу за о порядком продукцiю ((( або (((( таку, що ( \xF02D\xF020пiдслово xn. Застосуємо цю продукцiю до xn , тобто замiнимо в xn найлiвiше входження ( на (. Отримане слово позначимо xn+1. Якщо застосована на (n+1)-му етапi продукцiя нефiнальна, тобто (((, то переходимо до (n+2)-го етапу. Якщо ця продукцiя фiнальна, тобто ((((, то пiсля її застосування A зупиняється i A(x)=xn+1. Якщо ж на (n+1)-му етапi жодна продукцiя A не застосовна до xn+1, тобто в A немає продукцiї, лiва частина якої - пiдслово слова xn+1, то A зупиняється i A(x)=xn.

Якщо в процесi обробки слова x НА A не зупиняється нi на якому етапi, то вважаємо, що A(x) невизначене.

Нормальний алгоритм називають нормальним алгоритмом над алфавiтом T, якщо вiн є нормальним алгоритмом в деякому розширеннi T’(T. НА над T задає певне вiдображення T*\x2192T*, використовуючи в процесi обробки слiв допомiжнi символи поза алфавiтом T. Зупинка НА A над T при роботі над словом х(T*, результативна, коли вона вiдбулась на словi y(T*, iнакше вважаємо, що результат роботи A над х невизначений.