2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4
 
 
Сообщение02.03.2009, 22:40 
Аватара пользователя
$S \to ABC \to ABCC \to ABCABC \to ABCACABC \to 12313123 $

 
 
 
 
Сообщение02.03.2009, 22:44 
Аватара пользователя
juna
Убедили, возражение снимается.

 
 
 
 
Сообщение02.03.2009, 22:48 
Аватара пользователя
Честно говоря, было интересно доказать, что подобная грамматика действительно полностью описывает язык удвоенных последовательностей для $N=3$.

 
 
 
 
Сообщение02.03.2009, 22:56 
Аватара пользователя
juna
Для начала можно погенерировать все слова фиксированной длины и сравнить их количество с последовательностью A135473. Если будут сходится хотя бы в пределах первых двух десятков - это это будет веский аргумент в пользу вашего утверждения. А если обнаружится расхождение, то оно даст опровержение и можно будет уже детально искать контрпример фиксированной длины.

 
 
 
 
Сообщение17.03.2009, 09:52 
Аватара пользователя
Нашел контрпример.
Количества последовательностей по грамматике получились такие: 1, 3, 8, 21, 55.
Т.е. врать начинает с N=7. А именно
$S \to ABC \to ABCBC \to ABCBABC \to1232123$
последнее не входит в язык удвоенных последовательностей.

 
 
 [ Сообщений: 50 ]  На страницу Пред.  1, 2, 3, 4


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