Задайте нормальный алгоритм Маркова, реализующий умножение двух чисел, представленных символами 1.

А)сbc;

Б)ссbсbbс; в)сbасbа; г)сbаbс.

2. В алгоритмах Маркова дана система подстановок в алфавите А={а, b, с}: сb аbс, bас ас, саb b. Преобразуйте с помощью этой системы слово bсаbасаb:

А)ссb;

Б)саb; в)сbс; г)bсааb.

3. В алгоритмах Маркова дана система подстановок в алфавите А={а, b, с}: b асс, са ассс, аа , сссс .

А) Найдите слова, в которые этот алгоритм перерабатывает слова сасb и bb.

Б) Покажите, что алгоритм применим к любому исходному слову и перерабатывает его в одно из восьми слов (определите эти слова).

4. Пусть алфавит А и система подстановок имеют вид:

А={1, +}, 1+ +1, +1 1, 1 1. Покажите, во что перерабатывает этот алгоритм слово 1111+11+111.

5. Пусть алфавит А и система подстановок имеют вид:

А={ 1, +}, + , 1 1. Покажите, во что перерабатывает этот алгоритм слово 11+111+1+11.

Постройте нормальный алгоритм Маркова, реализующий вычитание двух целых чисел, представленных символами 1. Проверьте его работу на примерах.

Задайте нормальный алгоритм Маркова, реализующий умножение двух чисел, представленных символами 1.