Главная страница
Навигация по странице:

Нормальные алггоритмы Маркова+ Отчет 3. Решение bb ddd Пример 2 (замена и удаление символов)



Название Решение bb ddd Пример 2 (замена и удаление символов)
Анкор Нормальные алггоритмы Маркова+ Отчет 3.doc
Дата 12.04.2017
Размер 56 Kb.
Формат файла doc
Имя файла Нормальные алггоритмы Маркова+ Отчет 3.doc
Тип Решение
#718





Нормальные алгоритмы Маркова

Пример 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'>Решение.

baab

Пример 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

Решение.

*000*

*101*

*210*

*311*

* |

*
Проверка: 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 (например: bacbbbaaccbb).

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 переставить первый и последний символы.
написать администратору сайта