211
правок
Изменения
Нет описания правки
{{Определение
|definition =
'''Алфавит''' {{- --}} конечное непустое множество символов. Условимся обозначать алфавиты алфавит символом <tex>\Sigma</tex>.
}}
Наиболее часто используются следующие алфавиты:
# <tex>\Sigma=\{0, 1\}</tex> {{---}} бинарный или двоичный алфавит.
# <tex>\Sigma=\{a, b, ...,z\}</tex> {{---}} множество строчных букв английского алфавита.
{{Определение
|definition =
'''Слово''' ('''цепочка''') {{---}} это конечная последовательность символов некоторого алфавита.
}}
{{Определение
|definition =
'''Слово''', или '''Пустая цепочка''' {{-- это конечная последовательность символов некоторого алфавита-}} цепочка, не содержащая ни одного символа. НапримерЭту цепочку, 01101 - это цепочка в бинарном алфавите обозначаемую <tex>\Sigma = {0,1}varepsilon </tex>. Цепочка 111 это тоже цепочка , можно рассматривать как цепочку в этом любом алфавите.
}}
{{Определение|definition ='''Пустая цепочкаДлина цепочки''' {{- это цепочка, не содержащая ни одного символа--}} число символов в цепочке. Эту цепочку обозначаемую Длину некоторой цепочки <tex> \varepsilon w</tex> обычно обозначают <tex>|w|</tex>, можно рассматривать как цепочку в любом алфавите. '''Длина цепочки''' - число символов в цепочке.}}
{{Определение
|definition =
'''Степени алфавита'''
Если <tex>\Sigma</tex> {{--- }} некоторый алфавит, то можно выразить множество всех цепочек определенной длины, состоящих из символов данного алфавита, используя знак степени. Определим <tex>\Sigma^k</tex>, как множество всех цепочек длины <tex>k</tex>, состоящих из символов алфавита <tex>\Sigma</tex>. Определим Множество всех цепочек над алфавитом <tex>\Sigma</tex> принято обозначать <tex>\Sigma^*</tex>, как то есть <tex>\Sigma^*=\left\{\Sigma^0, \Sigma^1, \Sigma^2, ...\right\}</tex>.
}}
|definition =
'''Конкатенация слов'''
Пусть <tex>x</tex> и <tex>y</tex> {{- --}} цепочки. Тогда <tex>xy</tex> обозначает их '''конкатенацию'' (соединение)', т.е. цепочку, в которой последовательно записаны цепочки x и y.
}}
* Ассоциотивность <tex>(\alpha\beta)\gamma=\alpha(\beta\gamma)</tex>
* <tex>\exists \varepsilon </tex> (нейтральный элемент), такой, что <tex>\alpha\varepsilon=\varepsilon\alpha=\alpha</tex>
Таким образом мы получаем '''свободный моноид слов'''.
{{Определение|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</tex> для некоторого <tex>\gammadelta</tex>. }}
{{Определение
|definition =
'''Язык''' {{- --}} множество строчек, каждая из которых принадлежит <tex>\Sigma^*</tex>, где <tex>\Sigma</tex> {{--- }} некоторый фиксированный алфавит.
}}
Если <tex>\Sigma</tex> {{- --}} алфавит, и <tex>L \subseteq \Sigma^*</tex>, то <tex>L</tex> {{-- -}} это '''язык над''' <tex>\Sigma</tex>, или '''в''' <tex>\Sigma</tex>. Отметим, что язык в <tex>\Sigma</tex> не обязательно должен содержать цепочки, в которые входят все символы <tex>\Sigma</tex>. Поэтому, если известно, что <tex>L</tex> является языком в <tex>\Sigma</tex>, то можно утверждать, что <tex>L</tex> {{--- }} это язык над любым алфавитом, содержащим <tex>\Sigma</tex>.
