Изменения

Перейти к: навигация, поиск
м
Примеры
{{Определение
|id=alphabet
|definition =
'''Алфавит''' (англ. ''alphabet'') {{---}} конечное непустое [[Множества|множество]] символов. Условимся обозначать алфавит большой греческой буквой <tex>\Sigma</tex>.
Наиболее часто используются следующие алфавиты:
* <tex>\Sigma=\{0, 1\}</tex> {{---}} бинарный или двоичный алфавит.
* <tex>\Sigma=\{a, b, ...\dots,z\}</tex> {{---}} множество строчных букв английского алфавита.
* <tex>\Sigma = \left\{0, 1, 2, \dots, 9\right\} </tex> {{---}} алфавит цифр.
* <tex>\Sigma = \left\{\cdot, -\right\} </tex> {{---}} алфавит, лежащий в основе азбуки Морзе.
{{Определение
|id=string
|definition =
'''Слово''' (англ. ''string'') или '''цепочка''' {{---}} конечная последовательность символов некоторого алфавита.
{{Определение
|id=border
|definition='''Бордер''' (англ. ''circumfix'') строки <tex>\beta</tex> {{---}} строка <tex>\alpha : \beta = \gamma \alpha = \alpha \eta = \alpha \mu \alpha</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">\left\lfloor\frac{|\alpha|}{|\tau|} \right\rfloor</tex>.
Таким образом <tex>\alpha = </tex><tex dpi="140">\sum \limits_{i=1}^{\left\lfloor\frac{|\alpha|}{|\tau|} \right\rfloor}</tex><tex> \tau + \tau[1 \dots |\alpha| \bmod |\tau|]</tex>.
}}
Пусть <tex>\beta = abr\underline{aca}dabra</tex>, тогда <tex>\alpha = aca</tex> {{---}} подстрока строки <tex>\beta</tex>.
 
{{Определение
|id=repetition
|definition='''Тандемным повтором''' (англ. ''repetition'') называется непустая строка вида <math>\alpha\alpha</math>.
}}
 
{{Определение
|id=palindrome
|definition='''Палиндромом''' (англ. <i>Palindrome</i>) называется строка вида <tex>\alpha\overline{\alpha}</tex> или <tex>\alpha c\overline{\alpha}</tex>, где <tex>\overline{\alpha}</tex> {{---}} развернутая строка <tex>\alpha</tex>, <tex>c</tex> {{---}} любой символ.
}}
{{Определение
''или''
2. <tex> \mathcal {9} \exists k : k \leqslant \min(|\alpha|, |\beta|) </tex> и <tex> \alpha[k] < \beta[k] </tex>, при этом <tex> \mathcal {8} \forall j < k : \alpha_j = \beta_j </tex>
}}
* <tex>(\{0\}\{0\}^*) \cup (\{1\}\{1\}^*)</tex> {{---}} аналогично предыдущему, но не содержит пустую строку.
* <tex>(\{0\} \cup \{1\})^* = \{0, 1\}^*</tex> {{---}} содержит все двоичные векторы и пустую строку.
* Если <tex>L_p</tex> — язык десятичных представлений всех простых чисел, то язык <tex>(L_p \setminus (\{3\}\{1,2,3,4,5,6,7,8,9,0\}^*))\ \ </tex> будет содержать десятичные представления простых чисел, не начинающихся с тройки.
* <tex>\{\mathrm{ab, ba, bba, abab, aa}\}a^{-1} = \{\mathrm{b, bb, a}\}</tex>.
385
правок

Навигация