В алфавите племени Абба есть только две буквы «а» и «б». В языке
этого племени не каждый набор букв является словом. Слова образуются
по следующим правилам:
(Π1) буква «а» является словом;
(Π2) из любого слова можно получить новое слово, добавив в конце
букву «б»;
(Π3) если в каком-либо слове встречается последовательность «ааа», то
новое слово может быть получено заменой «ааа» буквой «б»;
(Π4) если в каком-либо слове встречается последовательность «ббб», то
новое слово может быть получено вычёркиванием этой последовательности;
(Π5) из любого слова можно получить новое слово путём приписывания
к первому справа его же.
1. В данном пункте нас будут интересовать возможные значения длин
слов в языке племени Абба.
(a) Существует ли в языке племени Абба слово длины 100? А 2021?
Если да, то постарайтесь привести соответствующие примеры слов.
(b) Какие значения может принимать длина слов в языке племени
Абба?
2. (a) Верно ли что «абба» является словом в языке племени Абба?
(b) Покажите, что «бабббабб» является словом в языке племени Абба.
(c) Докажите, что «баабаабаа» не является словом в языке племени
Абба.
(d) Приведите как можно больше слов языка племени Абба, состоящих из 5 букв.
(e) Приведите как можно больше слов языка племени Абба, состоящих из 6 букв.
3. Приведите какой-либо алгоритм определения того, как по заданной
последовательности букв выяснить, является ли она словом в языке
племени Абба или нет.
4. Предложите собственные обобщения и направления исследования этой
задачи и изучите их.