Задача 69859 Рассмотрим бесконечные слова в алфавите...

63b55b6c61079b77ceefa2dd

06.03.2023 19:20:14

Рассмотрим бесконечные слова в алфавите {a,b}. Пусть слово ab запрещено. Сколько имеется разрешенных бесконечных слов?

63fc9b4a1a353e3d161cc33d

08.03.2023 01:24:19

★

Количество разрешенных слов длины n, которые заканчиваются на символ "a", а через G(n) - количество разрешенных слов длины n, которые заканчиваются на символ "b". Тогда количество разрешенных слов длины n+1 можно выразить через F(n) и G(n) следующим образом:

F(n+1) = G(n) (если слово заканчивается на "a", то следующий символ должен быть "b", то есть слово длины n+1 заканчивается на "ab", что запрещено)
G(n+1) = F(n) + G(n) (если слово заканчивается на "b", то следующий символ может быть как "a", так и "b")

Из начальных условий F(1) = 1 и G(1) = 1 можно рекурсивно вычислить значения F(n) и G(n) для любого n. Например, для n=2 получаем:

F(2) = G(1) = 1
G(2) = F(1) + G(1) = 2

Для n=3:

F(3) = G(2) = 2
G(3) = F(2) + G(2) = 3

И так далее. Легко заметить, что F(n) и G(n) представляют собой последовательности чисел Фибоначчи, начиная с F(1) = 1, F(2) = 1. Таким образом, количество разрешенных бесконечных слов равно бесконечности, так как количество разрешенных слов каждой длины бесконечно, и каждой длине соответствует бесконечное количество слов.