Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
Версия от 19:54, 27 октября 2011; Kirelagin (обсуждение | вклад)
Определение: |
Алфавит — конечное непустое множество. Условимся обозначать алфавит символом | .
Наиболее часто используются следующие алфавиты:
- — бинарный или двоичный алфавит.
- — множество строчных букв английского алфавита.
Определение: |
Слово (цепочка) — конечная последовательность символов некоторого алфавита. |
Определение: |
Пустая цепочка — цепочка, не содержащая ни одного символа. Эту цепочку, обозначаемую | , можно рассматривать как цепочку в любом алфавите.
Определение: |
Длина цепочки — число символов в цепочке. Длину некоторой цепочки | обычно обозначают .
Определение: |
— множество цепочек длины над алфавитом . |
Определение: |
— множество всех цепочек над алфавитом . |
Определение: |
Язык над алфавитом | — некоторое подмножество . Иногда такие язык называют формальными, чтобы подчеркнуть отличие от языков в привычном смысле.
Отметим, что язык в не обязательно должен содержать цепочки, в которые входят все символы . Поэтому, если известно, что является языком над , то можно утверждать, что — это язык над любым алфавитом, являющимся надмножеством .
Определение: |
Пусть | . Тогда обозначает их конкатенацию, т.е. цепочку, в которой последовательно записаны цепочки x и y.
Свойства
Таким образом, мы получаем свободный моноид слов.