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

2012-05-31T13:43:25Z

178.178.19.204: sigma star index set fixup

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

{{Определение
|definition =
'''Алфавитом''' <tex>\Sigma</tex> называется конечное непустое множество элементов, называемых символами.
}}

{{Определение
|definition =
'''Нейтральным элементом''' (пустой строкой) <tex>\varepsilon \in \Sigma^{0}</tex> называется элемент, для которого верно <tex>\alpha\varepsilon=\varepsilon\alpha=\alpha</tex>.
}}

{{Определение
|definition =
'''Цепочкой''' (словом, строкой) конечной длины обозначим <tex>\Sigma^* : \Sigma^* = \bigcup\limits_{n = 0}^\infty \Sigma^n</tex>.
}}

{{Определение
|definition =
'''Конкатенацией''' строк <tex>\alpha \in \Sigma^k</tex> и <tex>\beta \in \Sigma^m</tex> является строка <tex>\alpha\beta \in \Sigma^{k+m}</tex>. Конкатенация является ассоциативной операцией.
}}

<tex>\Sigma^*</tex> с операцией конкатенации и нейтральным элементом <tex>\varepsilon</tex> образуют моноид. Данный моноид совпадает со свободным над <tex>\Sigma</tex>.

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

{{Определение
|definition =
<tex>\alpha</tex> называется '''префиксом''' <tex>\beta</tex>, если <tex>\beta = \alpha \gamma</tex>. Аналогично определяется '''суффикс''' строки.
}}

Пусть <tex>\beta = abracadabra</tex>, тогда
*если <tex>\alpha = abrac</tex>, то <tex>\alpha</tex> является префиксом <tex>\beta</tex>
*если <tex>\alpha = adabra</tex>, то суффиксом.

{{Определение
|definition =
<tex>\alpha</tex> называется '''бордером''' <tex>\beta</tex>, если <tex>\alpha</tex> одновременно является и суффиксом и префиксом.
|id=border
}}

Пусть <tex>\beta = abracadabra</tex>, тогда <tex>\alpha = abra</tex> будет бордером <tex>\beta</tex>.

{{Определение
|definition =
<tex>p</tex> называется '''периодом''' <tex>\alpha</tex>, если <tex>\forall i = 1 \ldots n - p</tex> <tex>\alpha [i] = \alpha[i + p]</tex>.
|id=border
}}

{{Определение
|definition =
Пусть строка <tex>\alpha \in \Sigma^m</tex> имеет период <tex>p</tex>, <tex>r = m / p</tex> и <tex>\beta \in \Sigma^p</tex>. Тогда декомпозиция <tex>\alpha = \beta^r </tex> называется '''нормальной формой''' строковой последовательности <tex>\alpha</tex>.
}}

{{Определение
|definition =
Строка <tex>\alpha</tex> называется примитивной, если <tex>p = m -</tex> максимальный период (т.е. <tex>r = 1</tex>).
}}

{{Определение
|definition =
Если <tex>r \ge 2</tex>, то строка <tex>\alpha</tex> называется '''сильнопериодической''', если <tex>1 < r < 2</tex>, то '''слабопериодической'''. Если <tex>r</tex> целое и <tex>r \ge 2</tex>, то строка <tex>\alpha</tex> называется '''строгопериодической''' (или просто '''периодической''').
}}

Строка <tex>aaabaabab</tex> - примитивная <tex>(p = m)</tex>.

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

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

{{Определение
|definition =
Строка <tex>\alpha</tex> является '''подстрокой''' <tex>\beta</tex>, если <tex>\beta = \gamma \alpha \delta</tex>.
}}

Строка <tex>\alpha = aca</tex> является подстрокой <tex>\beta = abracadabra</tex>.

{{Определение
|definition =
Строка <tex>\alpha \le \beta</tex>, если:
* <tex>\alpha</tex> префикс <tex>\beta</tex>
* <tex>\gamma</tex> общий префикс <tex>\alpha</tex> и <tex>\beta</tex>, <tex>\alpha = \gamma c \delta</tex>, <tex>\beta = \gamma d \xi</tex> и <tex>c < d</tex>
}}

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Викиконспекты - Вклад участника [ru]

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