Лекція 4. Нормальні алгоритми Маркова.

План:

1 Означення і основні властивості НАМ.

2.Алгоритм роботи НАМ.

3. Приклади роботи НАМ.

4.Функції обчислюванні за Марковим.

Література:[1], [3], [10].

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

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

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

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

Якщо в процесі обробки слова x нормальним алгоритмом Aне зупиняється ні на якому етапі, то вважаємо, що A(x) невизначене. Тобто алгоритм до такого слова не застосовний.

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

Два нормальні алгоритми Маркова A i B вважаться еквівалентними відносно алфавіту T, якщо для всіх xÎT* A(x) та B(x) одночасно визначені або невизначені, та у випадку визначеності A(x)=B(x).

Функція називається обчислюваною за Марковим, або НА-обчислюваною, якщо існує нормальний алгоритм, який її обчислює.

Наведемо приклади нормальних алгоритмів Маркова.

Приклад 1. Нормальний алгоритм Маркова, який кожне слово виду a^x переводить в слово (тобто по суті задає функцію 2^х в розширеному алфавіті Т=(а,d, λ)).da ® add

ad ® d

d ® .d

λ ® d

Приклад 2. Нормальний алгоритм Маркова, який реалізує функцію f(x,y)=x-y алфавіті Т=(1, -, λ) .

1-1 ® -

1- ® . λ

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Лекція 3. Машини з натуральнозначними регістрами.	\|	Лекція 5 . Співідношення між різнимим формальними уточненнями АОФ. Теза Чорча.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.