Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
Версия от 09:18, 3 октября 2010; 192.168.0.2 (обсуждение)
Алфавит и Слово
Алфавит - конечное непустое множество символов. Условимся обозначать алфавиты символом
.Слово, или цепочка - это конечная последовательность символов некоторого алфавита. Например, 01101 - это цепочка в бинарном алфавите
. Цепочка 111 это тоже цепочка в этом алфавите. Пустая цепочка - это цепочка, не содержащая ни одного символа. Эту цепочку обозначаемую , можно рассматривать как цепочку в любом алфавите. Длина цепочки - число позиций для символов в цепочке. Степени алфавита Если - некоторый алфавит, то можно выразить множество всех цепочек определенной длины, состоящих из символов данного алфавита, используя знак степени. Определим , как множество всех цепочек длины k, состоящих из символов алфавита .
Язык - множество строчек, каждая из которых принадлежит , где - некоторый фиксированный алфавит. Если - алфавит, и
Конкатенация
Свободный моноид слов