2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4
 
 
Сообщение02.03.2009, 22:40 
Заслуженный участник
Аватара пользователя


07/03/06
2114
Москва
$S \to ABC \to ABCC \to ABCABC \to ABCACABC \to 12313123 $

 Профиль  
                  
 
 
Сообщение02.03.2009, 22:44 
Модератор
Аватара пользователя


11/01/06
5710
juna
Убедили, возражение снимается.

 Профиль  
                  
 
 
Сообщение02.03.2009, 22:48 
Заслуженный участник
Аватара пользователя


07/03/06
2114
Москва
Честно говоря, было интересно доказать, что подобная грамматика действительно полностью описывает язык удвоенных последовательностей для $N=3$.

 Профиль  
                  
 
 
Сообщение02.03.2009, 22:56 
Модератор
Аватара пользователя


11/01/06
5710
juna
Для начала можно погенерировать все слова фиксированной длины и сравнить их количество с последовательностью A135473. Если будут сходится хотя бы в пределах первых двух десятков - это это будет веский аргумент в пользу вашего утверждения. А если обнаружится расхождение, то оно даст опровержение и можно будет уже детально искать контрпример фиксированной длины.

 Профиль  
                  
 
 
Сообщение17.03.2009, 09:52 
Заслуженный участник
Аватара пользователя


07/03/06
2114
Москва
Нашел контрпример.
Количества последовательностей по грамматике получились такие: 1, 3, 8, 21, 55.
Т.е. врать начинает с N=7. А именно
$S \to ABC \to ABCBC \to ABCBABC \to1232123$
последнее не входит в язык удвоенных последовательностей.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 50 ]  На страницу Пред.  1, 2, 3, 4

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: choocha, nimepe


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group