ВУЗ:
Составители:
другой стороны, результат ее выполнения. Пусть сасвА
=
и аввВ = . Тогда
сасваввАВ =
,
аввсасвВА =
. Длина конкатенации равна сумме длин образующих
ее слов.
Ясно, что конкатенация является всюду определенной и
ассоциативной, но не коммутативной операцией, т.е. для любых
*,, АСВА
∈
имеет место:
АВССАВВСА == )()( и
В
ААВ
≠
. Кроме того, АЕАА
Е
== , где Е
играет роль единичного элемента. Поэтому множество А* по операции
конкатенации является свободной подгруппой над А . Причем элементы А
являются образующими этой подгруппы.
Пусть
YXAQP ,,,, - различные слова в алфавите А и пусть
X
P
Y
A
=
.
Тогда слова
YPX ,, называются вхождениями в слово А. Слова PXX ,, ,
X
P
Y
называются подсловами А.
Пусть имеется подстановка вхождения слова Q вместо слова Р, и
наоборот, т.е. Р ∼ Q. Тогда слову А можно поставить в соответствие слово В
и, наоборот, из слова В получить слово А.
Пример. Если
араР = , а лоQ
=
, то слову дарапA
=
соответствует слово
длопВ = , и наоборот.
Подобные соотношения называются соотношениями Туэ (по имени
норвежского математика). Они приводят к одному из вариантов
ассоциативного исчисления.
Два слова А и В называются смежными, если одно из них получено из
другого однократным применением соотношений Туэ. В общем случае
можно допустить несколько последовательных применений соотношений
Туэ. Пусть А -
некоторый алфавит и
1
: PR ∼
n
PQ ,...,
1
∼
n
Q - систем соотношений
Туэ. Говорят, что слово В
о
соотносимо со словом В
р
, если существует
последовательность слов В
о
,…, В
р
, таких, что B
i
смежно с B
i-1
для pi ,...,1
=
.
Будем считать, что любое слово соотносимо с самим собой. Тогда
соотносимость будет рефлексивным, симметричным и транзитивным
отношением, т.е. отношением эквивалентности. Это позволяет соотносимые
Страницы
- « первая
- ‹ предыдущая
- …
- 11
- 12
- 13
- 14
- 15
- …
- следующая ›
- последняя »
