@aaayyy

Здравствуйте. Мне понадобилось быстро и вкратце разобраться с алгоритмами Маркова, я только что начала о них читать. В книге "Теория алгоритмов" авторов Матроса и Поднебесной я увидела такой пример:

Построить НАМ, заменив в алфавите A={a, b, c} все буквы a на c. Используем символ * для расширения алфавита A. Схема нормального алгоритма будет иметь следующий вид:

*a -> c*

*b -> b*

*c -> c*

* -> . _

_ -> *


Например: aacbab -> *aacbab -> c*acbab -> cc*cbab -> ccc*bab -> cccb*ab -> cccbc*b -> cccbcb* -> cccbcb

Где _ пустой символ. В учебнике указано, что левая часть подстановки м.б. пустым символом. Точка - признак заключительной подстановки. Указано также, что если в схеме нет больше подходящих формул подстановки, процесс построения последовательности считается завершившимся.

Вопрос: почему нельзя просто написать a -> c ?

Или все таки там написано нечетко и процесс построения последовательности считается завершившимся только если применена формула с точкой?

0