Удвоение в конечных последовательностях

[juna]

$S \to ABC \to ABCC \to ABCABC \to ABCACABC \to 12313123 $

[maxal]

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

[juna]

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

[maxal]

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

[juna]

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