B |→ab

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

Пример 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 (использование спецзнака)

А ={ 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 |→aa

b |→ab

* | →

→*

Пример 6 (перемещение спецзнака)

А ={ a, b }. Требуется приписать символ a к концу слова Р.

Например: bbab → bbaba

Дата добавления: 2015-09-02