Сразу оговорюсь, что тема постилась здесь много времени назад. И тогда меня почти уговорили, что решение бесконечно, но точного ответа не было. Недавно я отрыл в памяти эту задачу. Итак:

В языке состоящем из трех букв (a,b,c) все слова (конечные последовательности букв) имеют свой смысл.
Если в слове есть две подряд идущие одинаковые подпоследовательности букв, то можно написать это слово с одной такой подпоследовательностью с тем же смыслом (слова эквивалентны).
Например: abcbca = abca.
Вопрос: в этом языке конечное или бесконечное число смыслов слов (не эквивалентных слов)?

Сразу отмечу, что если кто-то думает (как и я раньше), что это равнозначно анализу числа несократимых слов, то это не так. Вот другой пример:
abc=abcbc=abcbabcbc=abcbabc
у двух разных несократиых слов может быть один и тот же смысл.

Ку — (с краткого словаря - все остальные слова) произносится при ритуальном приседании, а также при простом общении в результате чего один гуманоид (пацак или чатланин) должен прочесть мысли другого, сказавшего этот короткий призыв к беcсловесному общению на одном из плюканских языков.

Кю — допустимое в обществе ругательство.

Ы — универсальный союз и эмоциональное высказывание. По частоте употребления находится на втором месте после слова «Ку». Также служит в качестве второй по важности (после «Ку») мелодической составляющей в вокальной традиции носителей языка.

(0) Некрасивый язык, читать неудобно, произносить тоже, кто на таком писать будет?

хм, непонятно как быть с однобуквенными, но вообще вижу только 2-х буквенные варианты без сокращений
aa,ab,ac,ba,bb,bc,ca,cb,cc
или тут где-то подвох? :)

(3) полностью все слова длиной 1 и 2 буквы
a
b
c
aa=a
ab
ac
ba
bb=b
bc
ca
cb
cc=c

(0)Тогда немного усложнится условие:
"существует ли некоторая длина слова D, после которой все слова имеют более короткие аналоги?"

+5 =или указать переборно сокращение всех первоначально "несократимых" слов длины D+1, чтобы доказать конечность

(0) помню ветку, может не надо....

(5,6) конечность как бы теоретически доказана. Не хватает конструктивного алгоритма приводящая произвольное слово в минимальный аналог

(0) хммм.. А почему сие чудо именуется языком? Для передачи информации без потерь не пригодно ведь?

(5) "все" - нет

с большим трудом смог показать эквивалентность abcabac и abcbac. Частично расчет велся машинно.

(0) Хм в той ветке я даже доказательство приводил (наметки доказательства)

(12) а можно бы ее найти?

а в русском языке эти три буквы какие?

(14) матофильтр не пропустит...

Будем строить бесконечную последовательность правильных слов. Пусть у нас есть тройка слов
M=(M_1,M_2,M_3), такая что если в правильном слове X, заменить a на M_1, b на M_2, c на M_3[/MATH], то получится тоже правильное слово X’.

Пусть тройка M удовлетворяет свойствам:
1. M_1=AB, M_2=AC, M_3=AD. Причем B<>C, B<>D, C<>D.
2. Любая комбинация, состоящая из одного, двух (различных) и трех (среднее слово не равно крайним) слов из М есть:
2.1. Правильные слова
2.2. Слово A в них встречается только в начале слов M_1,M_2,M_3 и больше нигде.

Теорема:
Пусть тройка слов M удовлетворяет вышеприведенным свойствам. Тогда если в правильном слове X, заменить a на M_1, b на M_2, c на M_3, то получится тоже правильное слово X’.

Доказательство:
1. Предположим, что X’ неправильное слово. Тогда в нем должна содержаться последовательность вида E'_1E'_2, где E'_1=E'_2.
2. Если E'_1 начинается с M_1 или M_2 или M_3. Тогда E'_1 и E'_2 состоят целиком из последовательности одинаковых слов из M (это следует из свойств 1 и 2 тройки M). Но это невозможно, так как тогда E_1=E_2, что противоречит утверждению, что X правильное слово.
3. Итак E'_1 начинается где то с середины некоторого слова из M. Пусть E'_1=K'_1F'_1H'_1, где K'_1 хвостик слова из M; H'_1 начало слова из M; F'_1 состоит из целых слов из M либо пусто.
4. Анологично E'_2=K'_2F'_2H'_2.
5. Легко убедиться, что F'_1= F'_2. То есть состоят из одинаковой последовательности слов из M.
6. Тогда получается K'_1= K'_2; H'_1= H'_2; H'_1K'_2 слово из M.
7. Но в этом случае у нас в X’ есть последовательность M_i,FM_j,FM_l. Причем в последовательности M_i,M_j,M_l  есть две подряд идущие одинаковые последовательности K'_1,H'_1 и K'_2,H'_2, что противоречит свойству 2.1 тройки M.
8. Вывод. Гипотеза, что X’ неправильное слово неверна. Значит X’ правильное слово.

Осталось только найти тройку M удовлетворяющую условиям теоремы.

Слова удовлетворяющие условиям теоремы:
abcabac
abcacbacabacb
abcacbacabcbacbcabcb

(16)
Вася! Ей богу, тебе заняться чтоли нечем в субботу, кроме как какие-то задачки решать? :)

(17) умение мыслить абстрактно отличает нас от животных.
короче не хрюкай.

(16)
"Предположим, что X’ неправильное слово. Тогда в нем должна содержаться последовательность вида E'_1E'_2, где E'_1=E'_2."
А теперь осталось посмотреть контрпример в (0) что
abc=abcbc=abcbabcbc=abcbabc
Правое слово (Х) - несократимое, но "неправильное" в том смысле, что оно эквивалентно более короткому слову.
(10)
А показать?

(19) Понятно.

Бесконечность множества доказывает сам факт существования ирациональных чисел.

Шо-то моя не понимать, как это в примере получилось, что:
abc=abcbabc
Ведь в правом слове нет идущих ПОДРЯД подпоследовательностей?

(22) Да, моя тоже

(22) +1 так же не очевидна эквивалентность abcbc=abcbabc

(22) А, сорри, мая тупой
Мая всё панимать
Афтар прав :)

(16) то есть здесь неверное доказательство?

Есть мнение, что задача подобна описанию иррациаонального числа десятичной дробью - она будет бесконечная и периодическая.
Другими словами, если у нас есть ABСABBСABC... , то мы получаем бесконечное слово (непериодически вставляя в нужные места по одному B).
Если, конечно, мы предполагаем, что нельзя сокращать пары, идущие не подряд.
Если же ABCAB=ABC, что вообще странно, так как ABCABC=ABCC=AABC и т.д., то число слов будет явно конечным.

(27)
"Если же ABCAB=ABC"
это откуда? и остальные выводы из этого?

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

+(21)
+(27)
Да, ход рассуждения был таков:
Иррациональные числа существуют,
берем любое иррациональное число и представляем его в троичной системе счисления.
В троичной системе, число останется иррациональным, то есть не будет иметь в конце периодически повторяемой подпоследовательности, таким образом получаем бесконечную последовательность.

Но я уже понял свою ошибку.
Ведь не из чего не следует что в последовательности не найдется одинаковых рядом стоящих подпоследовательностей,
которые, после сокращения, могут войти в другую сокращаемую подпоследовательность.
Таким образом, это число может оказаться бесконечно сокращаемым.

Так что это не доказательство!
Но может кого на мысль наведет.

(26) Не обратил внимания, что постановка задачи изменилась. В (16) доказательство, что несокращаемых слов бесконечное множество. SUA в (19) на это мне уже указал.

(27)ABCA(B)(B)C...=(ABC)(ABC)...=ABC и даже просто добавлять не получится :)

Подниму ветку.
Итак несокращаемые слова ABC=ABCBABC эквиваленьны по смыслу, где A,B,C любые буквосочетания.
Вопрос. Есть ли еще подобные эквивалентности между несокращаемыми словами? Или вышеприведенное единственно?

(0)Йух

(33) ABCABAC=ABCBAC

(33)Очевидно что есть. Меняем А, В, С на последовательности и наслаждаемся :)

Может объявим конкурс на самое длинное несокращаемое слово? :)
Каждый имеет одну попытку.

(37) ABACBCAC

Я так и не понял одного - как именно можно сокращать слова по условию задачи, а как нет.

(39) элементарным преобразованием слова назовем:
1. сокращение одной из двух соседних одинаковых подряд идущих подпоследовательностей. Например ABCBCA=A(BC)(BC)A -> ABCA
2. дописывание любой подпоследовательности сразу за ней. Например ABCA=A(BC)A -> A(BC)(BC)A=ABCBCA. Обратное преобразование к пункту 1.

Так вот эквивалентными словами назовем те, которые можно получить одно из другого за конечно число элементарных преобразований.

Так и не понял (24)...

(41) abcbc = abcbabc
abc = abcbc = abcbabcbc = abcbabc
1. abc = abc(bc) - добавляем bc справа
2. abcbc = (abcb)abcbc - добавляем abcb слева
3. abcbabc(bc) = abcbabc - убираем bc справа

(42) откуда у меня ощущение, что меня путем хитрых манипуляций хотят "с жэ два на е пять"? :)
сиравно не понял, пойду посплю, можт поможет...

Чем то эти преобразования похожи на формулы сокращенного умножения или формулы логики высказываний (булева алгебра)

Дык может разработать какую то форму записи слов (аналог СДНФ в булевой) к которой легко можно привести любое слово (нужны правила приведения)

(44)+ а вообще то это троичная арифметика какая то

(44) было бы прекрасно. лишь бы не мешало общности понятий. следующим то шагом будет переход к алфавиту из N букв