производящие функции для множеств..

[Gilb007]

Всем привет! Подскажите плиз как можно решить эти задачки..
******************************
Задача 1:
Найти производящие функции для множеств A и B,если:

a)А-множество слов в алфавите {0,1,2,3,4}, в которых после каждого блока из двоек следует блок из нулей четной длины;
b)B-множество слов в алфавите {0,1,2}, в которых нет подслова "012".

Задача 2:
Найти число троичных последовательностей длины n,в которых нет ни двух нулей,ни двух единиц,стоящих подряд.
******************************
Есть мысль решать первую задачу с помощью конечного автомата,но пока не могу подступиться.
Спасибо!

[Trotil]

Задача 2 есть здесь: http://www.fizmat.vspu.ru/konkurs/

[Gilb007]

Trotil,вы правы!спасибо!

кто поможет расколоть первую задачку?оч интересно

[VAL]

Gilb007 писал(а):

Всем привет! Подскажите плиз как можно решить эти задачки..
******************************
Задача 1:
Найти производящие функции для множеств A и B,если:
[...]
b)B-множество слов в алфавите {0,1,2}, в которых нет подслова "012".

Рекуррентное соотношение: $f(n) = 3f(n-1) - f(n-3)$.
Соответственно, производящая функция, $ \frac{1}{1-3x+x^3}$.

[Gilb007]

VAL и вам спасибо!

Возник новый вопрос.
************************
Найти производящию функцию для последовательности из алфавита {0,1,2} в которой нет двух нулей и двух единиц стоящих подряд.
************************

Решал с помощью конечного автомата так.
Построил полный ориентированный граф из 3- вершин (состояния "0","1" и "2").В вершинах "0" и "1" убрал петли (т.к нет двух подряд стоящих нулей и единиц),в состоянии "2" -оставил.Вход в 2-ке,выход-со всех вершин.
Потом построил матрицу инциденстностей и решал данную системе в полукольце.
Получил язык ,который допускает даннй атомат.
Но преподаватель мне говорит про какую-то неоднозначность.На вопрос как решить задачу сказал что просто на подборе попытаться постоить регулярное выражение для данного условия.

Что скажете?Кто прав?На какие теоремы ссылаться?