Задача №1427

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

Условие

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

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

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

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

Задание 2. Докажите, что нельзя путём разрешённых преобразований получить из последовательности AB последовательность BA.

Решение

Комментарии