- Решение. bb -> ddd Пример 2
- Итог: c-> bb |-> ddd Пример 3
- Решение. ba → ab Пример 4
- Решение. 1. a | → b | → Но
- * a | → * b | → Но
- Решение. * a | →aa * b | →ab * | → →* Пример 6
- Решение. *a → a* *b → b* * |→ a → *
- Решение. *aa → a*a *ab → b*a *ba → a*b *bb → b*b * | → → *
- Решение.
- Задачи для самостоятельного решения Замечание.
Нормальные алггоритмы Маркова+ Отчет 3. Решение bb ddd Пример 2 (замена и удаление символов)
 Скачать 56 Kb.
|
|
Нормальные алгоритмы Маркова Пример 1 (замена символов) А={a,b,c,d}. В слове Р требуется заменить все вхождения подслова bb на ddd. Например: abbcabbca → adddcabbca Решение. bb -> ddd Пример 2 (замена и удаление символов) А={a,b,c,d}. В слове Р требуется заменить первое вхождение подслова bb на ddd и удалить все вхождения символа c. Например: abbcabbca → adddabba Решение. 1. bb -> ddd с -> Но: abbcabbca → adddcabbca → adddcadddca → adddadddca → … 2. c -> bb->ddd Но: abbcabbca → abbabbca → abbabba → adddabba → adddaddda Итог: c-> bb |-> ddd Пример 3 (перестановка символов) А={a,b}. Преобразовать слово Р так, чтобы в его начале оказались все символы a, а в конце – все символы b. Например: babba → aabbb Решение.__ba_→_ab_Пример_4'>Решение. ba→ab Пример 4 (использование спецзнака) А={a,b}. Удалить из непустого слова Р его первый символ. Пустое слово не менять. Решение. 1. a |→ b |→ Но, bbaba -> bbba – удалили не первый символ 2. -> * *a |→ *b |→ Но: bbaba → *bbaba → **bbaba → ***bbaba → … Отсюда вытекает очень важное правило: если в НАМ есть формула с пустой левой частью (→β), то её место – только в самом конце НАМ. 3. *a |→ *b |→ → * Но: на пустом слове – будет зацикливание! Итог: *a |→ *b |→ * |→ → * Пример 5 (вставка символа) А={a,b}. Вставить в начало любого слова символ а. Пустое слово не менять. Например: babba → ababba Решение.__*a_→_a*__*b_→_b*_*_|→_a_→_*'>Решение. *a |→aa *b |→ab * |→ →* Пример 6 (перемещение спецзнака) А={a,b}. Требуется приписать символ a к концу слова Р. Например: bbab → bbaba Решение. *a→ a* *b→ b* * |→ a → * Прежде всего напомним, что формула →a приписывает символ a слева к слову P, а не справа. Чтобы приписать a справа, надо сначала пометить конец слова. Для этого воспользуемся спецзнаком, который поместим в конец P, а затем заменим его на a: P → … → P* → Pa Но как поместить спецзнак в конец слова? Делается это так: сначала спецзнак * приписываем слева к слову P, а затем «перегоняем» звёздочку через все буквы слова: bbab → *bbab → b*bab → bb*ab → bba*b → bbab* А как сделать такой перегон? Нетрудно заметить, что «перепрыгивание» звёздочки через какой-то символ ξ – это замена пары *ξ на пару ξ*, которая реалиизуется формулой *ξ→ξ*. Пример 7 (перенос символа через слово). А={a,b}. Перенести в конец непустого слова Р его первый символ. Пустое слово не менять. Например: bbaba → babab Решение. *aa→ a*a *ab→ b*a *ba→ a*b *bb→ b*b * |→ → * Проверка: bbaba → *bbaba → b*baba → ba*bba → bab*ba → baba*b → babab Пример 8 (фиксация спецзнаком заменяемого символа) А={0,1,2,3}. Пусть Р – непустое слово. Трактуя его как запись неотрицательного целого числа в четверичной системе счисления, требуется получить запись это- го же числа, но в двоичной системе. Например: 0123 → 00011011 Решение. *0→00* *1→01* *2→10* *3→11* * |→ →* Проверка: 0123 → *0123 → 00*123 → 0001*23 → 000110*3 → 00011011* -> 0001101 Пример 9 А={0,1,2,3, 4, 5, 6, 7}. Пусть Р – непустое слово. Трактуя его как запись неотрицательного целого числа в восьмеричной системе счисления, требуется получить запись этого же числа, но в двоичной системе. Например: 012345 → 000001010011100101 Задачи для самостоятельного решения Замечание. Из предложенного списка заданий решить любые 10. 1 A={f,h,p}. В слове P заменить все пары ph на f. 2 A={f,h,p}. В слове P заменить на f только первую пару ph, если такая есть. 3 A={a,b,c}. Приписать слово bac слева к слову P. 4 A={a,b,c}. Заменить слово P на пустое слово, т.е. удалить из P все символы. 5 A={a,b,c}. Заменить любое входное слово на слово a. 7 A={ | }. Считая слово P записью числа в единичной системе счисления, получить остаток от деления этого числа на 2, т.е. получить слово из одной палочки, если число нечётно, или пустое слово, если число чётно. 8 A={ | }. Считая слово P записью положительного числа в единичной системе счисления, уменьшить это число на 1. 9 A={ | }. Считая слово P записью числа в единичной системе счисления, увеличить это число на 2. 10 A={a,b,c}. Определить, входит ли символ a в слово P. Ответ (выходное слово): слово a, если входит, или пустое слово, если не входит. 11 A={0,1,2,3}. Преобразовать слово P так, чтобы сначала шли все чётныецифры (0 и 2), а затем – все нечётные. 12 A={a,b,c}. Преобразовать слово P так, чтобы сначала шли все символы a, затем – все символы b и в конце – все символы c. 13 A={a,b,c}. За первым символом непустого слова P вставить символ c. 14 A={a,b,c}. Из слова P удалить второй символ, если такой есть. 15 A={a,b,c}. Приписать слово abc справа к слову P. 16 A={a,b,c}. Удвоить каждый символ в слове P (например: bacb → bbaaccbb). 17 A={a,b,c}. В непустом слове P оставить только последний символ. 18 A={a,b,c}. Если слово P начинается с символа a, то заменить P на пустоеслово, а иначе P не менять. 19 A={a,b}. Перенести первый символ непустого слова P в конец слова. 20 A={a,b}. В непустом слове P переставить первый и последний символы. |