Алгоритм Маркова составляется из конечного упорядоченного множества подстановок – правил преобразования слова заменой его фрагментов. Правила преобразования (подстановки) выполняются поочередно над исходной (непустой строкой символов, пока не будет выполнено специальное завершающее правило. Каждый раз выполнение начинается с самой первой возможной подстановки.

Воспользуемся этим правилом. Получаем babcaba. В полученном слове babcaba снова возможна подстановка (1) → babcbab→ (3) babaacab→ (1) bbabacab→(1) bbbabcab→ (4) bbbabcbb→ (3)bbbabaacb→ (1) bbbbabacb→ (1) bbbbbabcb→ (3)bbbbbabaac→ (1)bbbbbbabac→ (1)bbbbbbbabc. Заверщающее правило (2) не было применено ни разу, и алгоритм завершил работу из-за невозможности выполнить ни одну заданную подстановку.

Ответ: bbbbbbbabc