напишите в отдельном посте определение всех понятий и свое утверждение
Давайте уж окончательную версию.
Определение 1. Cлово длины
на любом конечном алфавите
называется
допустимым, если
а) Каждая буква входит в слово ровно два раза.
б) Буква
первый раз (слева направо) входит в слово после буквы
.
Определение 2. Редукцией допустимого слова называется композиция некоторого числа следующих преобразований
1) Удаление двух стоящих рядом одинаковых букв.
2) Замена двух букв на одну, если буквы в слове расположены таким образом -
(в этом случае слово преобразуется к виду
).
Определение 3. Пусть
- допустимое слово длины
.
Редуцированное слово - слово длины
, полученное в результате редукции
и переименования букв на алфавите
по правилу (б) определения 1.
Определение 4. Допустимое или редуцированное слово следующего вида
называется
хорошим словом. Слово
-
пустое слово, т.е. слово без букв.
Определение 5. Буквы
и
в допустимом или редуцированном слове будем называть
дружественными, если они расположены в таком порядке -
.
Определение 6. Матрицей слова длины
называется
матрица
над полем
элементы которой определяются по следующему правилу. Если в слове две буквы с номерами
дружественные, тогда
. В противном случае
.
Утверждение. Слово является хорошим тогда и только тогда, когда ранг его матрицы .