211
правок
Изменения
м
{{Определение
|definition =
'''Степени алфавита'''
}}
'''Конкатенация слов'''
{{Определение
|definition =
Слово <tex>\alpha</tex> является '''префиксом''' <tex>\beta</tex>, если <tex>\exists \gamma : \beta = \alpha\gamma</tex>.
}}
{{Определение
|definition =
Слово <tex>\alpha</tex> является '''суффиксом''' <tex>\beta</tex>, если <tex>\exists \gamma : \beta = \gamma\alpha</tex>.
}}
{{Определение
|definition =
Слово <tex>\alpha</tex> является '''подстрокой''' <tex>\beta</tex>, если <tex>\exists \gamma, \delta : \beta = \gamma\alpha\delta</tex>.
}}
Нет описания правки
# <tex>\Sigma=\{0, 1\}</tex> {{---}} бинарный или двоичный алфавит.
# <tex>\Sigma=\{a, b, ...,z\}</tex> {{---}} множество строчных букв английского алфавита.
{{Определение
|definition =
'''Длина цепочки''' {{---}} число символов в цепочке. Длину некоторой цепочки <tex>w</tex> обычно обозначают <tex>|w|</tex>.
}}
Если <tex>\Sigma</tex> {{---}} некоторый алфавит, то можно выразить множество всех цепочек определенной длины, состоящих из символов данного алфавита, используя знак степени. Определим <tex>\Sigma^k</tex> как множество всех цепочек длины <tex>k</tex>, состоящих из символов алфавита <tex>\Sigma</tex>. Множество всех цепочек над алфавитом <tex>\Sigma</tex> принято обозначать <tex>\Sigma^*</tex>, то есть <tex>\Sigma^*=\{\Sigma^0, \Sigma^1, \Sigma^2, ...\}</tex>.
{{Определение
|definition =
Пусть <tex>x</tex> и <tex>y</tex> {{---}} цепочки. Тогда <tex>xy</tex> обозначает их '''конкатенацию''', т.е. цепочку, в которой последовательно записаны цепочки x и y.
}}
Таким образом мы получаем '''свободный моноид слов'''.
{{Определение
