Основные определения, связанные со строками — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Базовые определения)
(Отношения между строками)
Строка 43: Строка 43:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Пусть строка <tex>x = \sum^n</tex> имеет минимальный период <tex>p</tex>, <tex>r = n / p</tex> и <tex>u = \sum^p</tex>. Тогда декомпозиция <tex>x = u^p </tex> называется '''нормальной формой''' строковой последовательности <tex>x</tex>.
+
<tex>p</tex> называется '''периодом''' <tex>\alpha</tex>, если <tex>\forall i = 1 \ldots n - p</tex> <tex>\alpha [i] = \alpha[i + p]</tex>.
 +
}}
 +
 
 +
{{Определение
 +
|definition =
 +
Пусть строка <tex>x = \sum^n</tex> имеет период <tex>p</tex>, <tex>r = n / p</tex> и <tex>u = \sum^p</tex>. Тогда декомпозиция <tex>x = u^p </tex> называется '''нормальной формой''' строковой последовательности <tex>x</tex>.
 
}}
 
}}
  

Версия 12:17, 22 апреля 2012

Базовые определения

Определение:
Алфавитом [math]\sum[/math] называется конечное непустое множество элементов, называемых символами.


Определение:
Цепочкой (словом, строкой) конечной длины обозначим [math]\sum^* : \sum^* = \bigcup\limits_{n \in \mathbb N} \sum^n[/math].


Определение:
Конкатенацией строк [math]\alpha = \sum^k[/math] и [math]\beta = \sum^m[/math] является строка [math]\alpha\beta = \sum^{k+m}[/math]. Конкатенация является ассоциативной операцией.


Определение:
Нейтральным элементом (пустой строкой) [math]\varepsilon \in \sum^{0}[/math] называется элемент, для которого верно [math]\alpha\varepsilon=\varepsilon\alpha=\alpha[/math].


Нейтральный элемент превращает [math]\sum^*[/math] в свободный моноид, порожденный [math]\sum[/math].

Отношения между строками

Определение:
[math]\alpha[/math] называется префиксом [math]\beta[/math], если [math]\beta = \alpha \gamma[/math]. Аналогично определяется суффикс строки.


Пусть [math]\beta = abracadabra[/math], тогда

  • если [math]\alpha = abrac[/math], то [math]\alpha[/math] является префиксом [math]\beta[/math]
  • если [math]\alpha = adabra[/math], то суффиксом.


Определение:
[math]\alpha[/math] называется бордером [math]\beta[/math], если [math]\alpha[/math] одновременно является и суффиксом и префиксом.


Пусть [math]\beta = abracadabra[/math], тогда [math]\alpha = abra[/math] будет бордером [math]\beta[/math].


Определение:
[math]p[/math] называется периодом [math]\alpha[/math], если [math]\forall i = 1 \ldots n - p[/math] [math]\alpha [i] = \alpha[i + p][/math].


Определение:
Пусть строка [math]x = \sum^n[/math] имеет период [math]p[/math], [math]r = n / p[/math] и [math]u = \sum^p[/math]. Тогда декомпозиция [math]x = u^p [/math] называется нормальной формой строковой последовательности [math]x[/math].


Определение:
Строка [math]x[/math] называется примитивной, если [math]r = 1[/math].


Определение:
Если [math]r \ge 2[/math], то строка [math]x[/math] называется сильнопериодической, если [math]1 \lt r \lt 2[/math], то слабопериодической. Если [math]r[/math] целое и [math]r \ge 2[/math], то строка [math]x[/math] называется строгопериодической (или просто периодической).


Строка [math]aaabaabab[/math] - примитивная [math](p = n)[/math].

Строка [math]abaababaabaab = (abaababa)(abaab)[/math] - слабопериодическая с периодом [math]p = 8[/math], порядком [math]r = 13/8[/math].

Строка [math]abaabaab = (aba)^2(ab)[/math] - сильнопериодическая с периодом [math]p = 3[/math], порядком [math]r = 8/3[/math].


Определение:
Строка [math]\alpha[/math] является подстрокой [math]\beta[/math], если [math]\beta = \gamma \alpha \delta[/math].


Строка [math]\alpha = aca[/math] является подстрокой [math]\beta = abracadabra[/math].


Определение:
Строка [math]\alpha \le \beta[/math], если:
  • [math]\alpha[/math] префикс [math]\beta[/math]
  • [math]\gamma[/math] общий префикс [math]\alpha[/math] и [math]\beta[/math], [math]\alpha = \gamma c \delta[/math], [math]\beta = \gamma d \xi[/math] и [math]c \lt d[/math]