Изменения
Нет описания правки
{{Определение
|definition='''Символ''' (англ. ''Symbolsymbol'') {{---}} объект, имеющий собственное содержание и уникальную читаемую форму.
}}
{{Определение
|definition='''Алфавит''' (англ. ''Alphabetalphabet'') <tex>\Sigma</tex> {{---}} непустое множество символов.
}}
* <tex>\Sigma = \left\{0, 1\right\} </tex> {{---}} бинарный алфавит.
* <tex>\Sigma = \left\{\cdot, -\right\} </tex> {{---}} алфавит, лежащий в основе азбуки Морзе.
* <tex>\Sigma = \left\{a, b, c, d, ... \dots, z\right\} </tex> {{---}} английский алфавит.* <tex>\Sigma = \left\{0, 1, 2, ...\dots, 9\right\} </tex> {{---}} алфавит цифр.
* Нотные знаки
{{Определение
|definition='''Нейтральный элемент''' {{---}} пустая строка <tex>\varepsilon</tex>: <tex>\varepsilon \in \Sigma^{0}</tex>. Для любой строки <tex>\alpha \in \Sigma^k</tex> верно: <tex>: \alpha\varepsilon=\varepsilon\alpha=\alpha</tex>.
}}
}}
Если <tex>\Sigma = \left\{0, 1\right\}</tex>, то <tex>\Sigma^* = \left\{\varepsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ... \dots \right\} </tex>.
{{Определение
|definition='''Цепочка''' (англ. ''Chainchain'') {{---}} элемент конечной длины из <tex>\Sigma^*</tex>.
}}
{{Определение
|definition='''Конкатенация''' (англ. ''Concatenationconcatenation'') {{---}} бинарная, ассоциативная, некоммутативная операция, определённая на словах данного алфавита. Конкатецния строк <tex>\alpha \in \Sigma^k</tex> и <tex>\beta \in \Sigma^m</tex> является строка <tex>\alpha\beta \in \Sigma^{k + m}</tex>.
}}
{{Определение
|definition='''Моноид''' (англ. ''Monoidmonoid'') {{---}} множество, на котором задана бинарная ассоциативная операция, обычно именуемая умножением, и в котором существует нейтральный элемент. <tex>\Sigma^*</tex> с операцией конкатенации и нейтральным элементом <tex>\varepsilon</tex> образуют моноид
}}
{{Определение
|id=prefix
|definition='''Префикс''' (англ. ''prefix'') строки <tex>\beta</tex> {{---}} строка <tex>\alpha</tex>: <tex>\beta = \alpha \gamma</tex>.
}}
{{Определение
|id=suffix
|definition='''Суффикс''' (англ. ''suffix'') строки <tex>\beta</tex> {{---}} строка <tex>\alpha</tex>: <tex>\beta = \gamma \alpha </tex>.
}}
{{Определение
|id=border
|definition='''Бордер''' (англ. ''circumfix'') строки <tex>\beta</tex> {{---}} строка <tex>\alpha</tex>: <tex>\beta = \gamma \alpha = \alpha \eta= \alpha \mu \alpha</tex>.
}}
Пусть <tex>\beta = \underline{abra}cad\underline{abra}</tex>, тогда <tex>\alpha = abra</tex> {{---}} бордер <tex>\beta</tex>. {{Определение|id=ind|definition=<tex>\alpha[i]</tex> {{---}} обращение к символу под номером <tex>i</tex> строки <tex>\alpha</tex>.}}
{{Определение
|id=period
|definition='''Период''' (англ. ''period'') строки <tex>\alpha</tex> {{---}} число <tex>p</tex>: <tex>\forall i = 1 \ldots |\alpha| - p,
\alpha [i] = \alpha[i + p]</tex>.
}}
{{Утверждение
|statement=Пусть известна строка <tex>\tau</tex> {{---}} период <tex>\alpha</tex> и <tex>|\alpha|</tex>, тогда можно восстановить всю строку <tex>\alpha</tex>.
|proof=Из определения периода строки следует, что <tex>\alpha[1...\dots |\tau|] = \alpha[|\tau| + 1...\dots 2*\cdot |\tau|] = ... \dots = \alpha[|\tau|*\cdot (k - 1) + 1...\dots |\tau|*\cdot k] </tex>, где <tex>k = </tex> <tex dpi="140">\lfloor\frac{|\alpha|}{|\tau|} \rfloor</tex>. Таким образом <tex>\alpha = </tex><tex dpi="140">\sum \sum_limits_{i=1}^{\lfloor\frac{|\alpha|}{|\tau|} \rfloor} </tex><tex> \tau + \tau[1...\dots |\alpha| mod \bmod |\tau|]</tex>.
}}
{{Определение
|id=substring
|definition='''Подстрока''' (англ. ''substring'') {{---}} некоторая непустая связная часть подпоследовательность подряд идущих символов строки.
}}
''или''
2. <tex> \mathcal {9} k : k\leqslant \min(|\alpha|, |\beta|): </tex> и <tex> \alpha[k] < \beta[k] </tex> и , при этом <tex> \mathcal {8} j < k ~: \alpha_j = \beta_j </tex>
}}
