Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
Версия от 01:51, 8 октября 2010; Sokolov Andrey (обсуждение | вклад)
Пустая цепочка - это цепочка, не содержащая ни одного символа. Эту цепочку обозначаемую
, можно рассматривать как цепочку в любом алфавите. Длина цепочки - число символов в цепочке.Шаблон:Определение степени алфавита
Свойства
- Ассоциотивность
- нейтральный элемент
Таким образом мы получаемсвободный моноид слов.
Слово
является префиксом , если для некоторого .Слово
является суффиксом , если для некоторого .Слово
является подстрокой , если для некоторого , .(
, могут быть пустыми)Если
- алфавит, и , то - это язык над , или в . Отметим, что язык в не обязательно должен содержать цепочки, в которые входят все символы . Поэтому, если известно, что является языком в , то можно утверждать, что - это язык над любым алфавитом, содержащим .