Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками

Алфавит и Слово

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

Слово, или цепочка - это конечная последовательность символов некоторого алфавита. Например, 01101 - это цепочка в бинарном алфавите [math]\Sigma = {0,1}[/math]. Цепочка 111 это тоже цепочка в этом алфавите. Пустая цепочка - это цепочка, не содержащая ни одного символа. Эту цепочку обозначаемую [math] \varepsilon [/math], можно рассматривать как цепочку в любом алфавите. Длина цепочки - число позиций для символов в цепочке. Степени алфавита Если [math]\Sigma[/math] - некоторый алфавит, то можно выразить множество всех цепочек определенной длины, состоящих из символов данного алфавита, используя знак степени. Определим [math]\Sigma^k[/math], как множество всех цепочек длины k, состоящих из символов алфавита [math]\Sigma[/math].

Язык - множество строчек, каждая из которых принадлежит [math]\Sigma^*[/math], где [math]\Sigma[/math] - некоторый фиксированный алфавит. Если [math]\Sigma[/math] - алфавит, и [math]\L \subseteq Sigma^*[/math] Конкатенация Свободный моноид слов