laboratorni_markov7

ЛАБОРАТОРНА РОБОТА № 7

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

Теоретичні відомості

Підстановки

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

Формулою підстановки називається запис виду α→β (читається "α замінити на β"), де α і β – будь-які слова (можливо, і порожні). При цьому α називається лівою частиною формули, а β – правою частиною.

Сама підстановка (як дія) задається формулою підстановки і застосовується до деякого слова Р. Суть операції зводиться до того, що в слові Р відшукується частина, співпадаюча з лівою частиною цієї формули (тобто з α), і вона замінюється на праву частину формули (тобто на β). При цьому інші частини слова Р (ліворуч і праворуч від β) не міняються. Слово, що вийшло, R називають результатом підстановки. Умовно це можна зображувати так:

Необхідні уточнення:

1. Якщо ліва частина формули підстановки входить в слово Р, то говорять, що ця формула застосовна до Р. Але якщо α не входить в Р, то формула вважається непридатною до Р, і підстановка не виконується.

2. Якщо ліва частина α входить в Р кілька разів, то на праву частину β, за визначенням, замінюється тільки перше входження α в Р:

3. Якщо права частина формули підстановки - порожнє слово, то підстановка α→ зводиться до викреслювання частини α з Р (відмітимо попутно, що у формулах підстановки не прийнято як-небудь означати порожнє слово) :

4. Якщо в лівій частині формули підстановки вказано порожнє слово, то підстановка →β зводиться, за визначенням, до приписування β ліворуч до слова Р :

З цього правила витікає дуже важливий факт: формула з порожньою лівою частиною застосована до будь-якого слова. Відмітимо також, що формула з порожніми лівою і правою частинами не міняє слово.

Визначення НАМ

Нормальним алгоритмом Маркова (НАМ) називається непорожній кінцевий впорядкований набір формул підстановки:

У цих формулах можуть використовуватися два види стрілок: звичайна стрілка (→) і стрілка "з крапкою" (→.). Формула із звичайною стрілкою називається звичайною формулою, а формула із стрілкою "з крапкою" – завершальною формулою. Різниця між ними пояснюється трохи нижче.

Записати алгоритм у виді НАМ – означає пред'явити такий набір формул.

Індивідуальні завдання.

Виберіть індивідуальне завдання відповідно варіанту.

1. Пусть для слов в алфавите А = {а, b, с, d) заданы следующие марковские подстановки: а) ab → dc; б) bc → а; в) dd → bb; г) ас → dc. Примените каждую из них к слову abcddacba.

2. Пусть для слов в алфавите А = {а, b, с} заданы следующие марковские подстановки: а) abc → ; б) bca → ; в) abca → a; г) a → b. Примените каждую из них к слову abcabcabcab максимально возможное число раз.

3. Пусть для слов в алфавите А = {а, b, с, d) заданы следующие марковские подстановки: а) cba → ; б) abc → ; в) da → ; г) dac → acd. Примените каждую из них к слову abcddacba.

4. Пусть для слов в алфавите А = {а, b, с} заданы следующие марковские подстановки: а) b → а; б) с → b; в) ab → bc; г) bc → са. Примените каждую из них к слову abcabcabcab максимально возможное число раз.

5. Пусть для слов в алфавите А = {а, b, с, d) заданы следующие марковские подстановки: а) а → bd б) cb d; . Примените каждую из них к слову abcddacba.

6. Пусть для слов в алфавите А = {а, b, с} заданы следующие марковские подстановки: а) ca → ab; б) cab → ; в) bcab → ; г) abca → a. Примените каждую из них к слову abcabcabcab максимально возможное число раз.

7. A={ | }. Вважаючи слово P записом позитивного числа в одиничній системі числення, зменшити це число на 1.

8. A={ | }. Вважаючи слово P записом числа в одиничній системі числення, збільшити це число на 2.

2