ВУЗ:
Составители:
слова называть эквивалентными и обозначать знаком ≈. Легко видеть, что
для любых слов Х и Y из
В
А ≈ следует
X
B
Y
X
A
Y
≈
.
Туэ сформулировал следующую проблему, известную под названием
«проблемы эквивалентности»: для любой пары слов в некотором алфавите
установить, являются они эквивалентными или нет.
Большой вклад в исследование этой проблемы внесли советские
математики А.А. Марков и Г.С. Цейтин.
Остановимся более подробно на этих вопросах. Введем сначала
следующие определения.
Слово
1−
А называется обращением (инверсией) слова А, если оно
образовано в точности из тех же вхождений, что и А, не взятых в обратном
порядке. Слово А называется симметричным, если оно совпадает со своей
инверсией.
Рассмотрим ассоциативное исчисление
},{ вaА
=
, аа∼Е, вв∼Е.
Сократить слово А в этом исчислении - значит образовать новое слово
В, смежное с А, которое короче А. Взяв некоторое слово за исходное, мы
можем путем последовательных сокращений образовать ряд слов, который
приведет к несократимому слову (возможно пустому).
Пример. Пусть
авввааввааавввА = , ававВ
=
, авааавваввваС
=
. Покажем
один из вариантов сокращения слова А:
ававввававвавввввааввваввваааааввваввввввввваааввваваа ≈
≈
≈
≈
≈ .
В результате получаем, что
В
А
≈
является несократимым в этом
исчислении. Существует несколько вариантов сокращения слова С, один из
которых имеет вид:
Евввввввввваааввввввавааавваввваввавввааваа
≈
≈≈
≈
≈
≈
.
Поэтому
ЕС ≈ .
Легко проверить, что результат не зависит от того, в каком порядке
выполняются сокращения. В каждом классе эквивалентности существует
ровно одно несократимое слово, которое называется каноническим
представителем этого класса.
Страницы
- « первая
- ‹ предыдущая
- …
- 12
- 13
- 14
- 15
- 16
- …
- следующая ›
- последняя »
