Изменения

|definition =

'''Алфавит''' - конечное непустое множество символов. Условимся обозначать алфавиты символом <tex>\Sigma</tex>.

}}

'''Слово''', или '''цепочка''' - это конечная последовательность символов некоторого алфавита. Например, 01101 - это цепочка в бинарном алфавите <tex>\Sigma = {0,1}</tex>. Цепочка 111 это тоже цепочка в этом алфавите.

''Пустая цепочка'' - это цепочка, не содержащая ни одного символа. Эту цепочку обозначаемую <tex> \varepsilon </tex>, можно рассматривать как цепочку в любом алфавите.

''Длина цепочки'' - число символов в цепочке.

'''Степени алфавита'''

Если <tex>\Sigma</tex> - некоторый алфавит, то можно выразить множество всех цепочек определенной длины, состоящих из символов данного алфавита, используя знак степени. Определим <tex>\Sigma^k</tex>, как множество всех цепочек длины <tex>k</tex>, состоящих из символов алфавита <tex>\Sigma</tex>. Определим <tex>\Sigma^*</tex>, как <tex>\Sigma^*=\left\{\Sigma^0, \Sigma^1, \Sigma^2, ...\right\}</tex>

'''Конкатенация слов'''

Пусть <tex>x</tex> и <tex>y</tex> - цепочки. Тогда <tex>xy</tex> обозначает их ''конкатенацию'' (соединение), т.е. цепочку, в которой последовательно записаны цепочки x и y.

''Свойства''