Задача №1426

Автор: А. Н. Журинский

Явления: грамматика формальная

Условие

Будем рассматривать последовательности, состоящие только из букв A и B (например, AABABB, AA, B и т. п.). Разрешается преобразовывать каждую из последовательностей следующим образом:

1. если в последовательности есть группа BA (подряд и именно в этом порядке), то её можно заменить на ABBB;
2. ABBB можно заменить (при тех же условиях) на BA;
3. можно вычеркнуть подряд идущую группу AA или BBBB;
4. между любыми двумя стоящими рядом буквами последовательности, или левее всех букв, или правее всех букв можно написать группу AA или BBBB.

К каждой последовательности можно применить любое из этих преобразований, к полученной последовательности — снова любое из этих преобразований и т. д.

Задание 1. Какую цепочку преобразований нужно применить к последовательности AB, чтобы получить из неё последовательность BBBA (известно, что это можно сделать)?

Задание 2. Какую цепочку преобразований нужно применить к последовательности AB, чтобы получить последовательность ABABAB?

Задание 3. Можно ли путём указанных преобразований из последовательности AB получить последовательность ABAB?

Решение

Комментарии