2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

 
 
 
 
Сообщение24.11.2008, 20:32 
Аватара пользователя
Задача 2 есть здесь: http://www.fizmat.vspu.ru/konkurs/

 
 
 
 
Сообщение24.11.2008, 21:03 
Trotil,вы правы!спасибо!

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

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

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

 
 
 
 
Сообщение09.12.2008, 19:44 
VAL и вам спасибо!

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

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

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

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group