Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками — различия между версиями
(→Свойства) |
(→Свойства) |
||
Строка 48: | Строка 48: | ||
==Свойства== | ==Свойства== | ||
− | * <tex>(\alpha\beta)\gamma=\alpha(\beta\gamma)</tex> | + | * <tex>\forall \alpha, \beta, \gamma. (\alpha\beta)\gamma=\alpha(\beta\gamma)</tex> |
− | * <tex>\alpha\varepsilon=\varepsilon\alpha=\alpha</tex> | + | * <tex>\forall \alpha, \beta. \alpha\varepsilon=\varepsilon\alpha=\alpha</tex> |
Таким образом, мы получаем '''свободный [[Моноид|моноид]] слов'''. | Таким образом, мы получаем '''свободный [[Моноид|моноид]] слов'''. |
Версия 17:51, 16 октября 2013
Определение: |
Алфавит — конечное непустое множество. Условимся обозначать алфавит символом | .
Наиболее часто используются следующие алфавиты:
- — бинарный или двоичный алфавит.
- — множество строчных букв английского алфавита.
Определение: |
Слово (цепочка) — конечная последовательность символов некоторого алфавита. |
Определение: |
Пустая цепочка — цепочка, не содержащая ни одного символа. Эту цепочку, обозначаемую | , можно рассматривать как цепочку в любом алфавите.
Определение: |
Длина цепочки — число символов в цепочке. Длину некоторой цепочки | обычно обозначают .
Определение: |
— множество цепочек длины над алфавитом . |
Определение: |
— множество всех цепочек над алфавитом . |
Определение: |
Язык над алфавитом | — некоторое подмножество . Иногда такие языки называют формальными, чтобы подчеркнуть отличие от языков в привычном смысле.
Отметим, что язык в не обязательно должен содержать цепочки, в которые входят все символы . Поэтому, если известно, что является языком над , то можно утверждать, что — это язык над любым алфавитом, являющимся надмножеством .
Определение: |
Пусть | . Тогда обозначает их конкатенацию, т.е. цепочку, в которой последовательно записаны цепочки x и y.
Свойства
Таким образом, мы получаем свободный моноид слов.
Операции над языками
Пусть
и — языки. Тогда над ними можно определить следующие операции.- Теоретико-множественные операции:
- — объединение,
- — пересечение,
- — разность,
- — дополнение.
- Конкатенация: .
- Конкатенация с обратным языком: ; конкатенация с обратным словом: .
- Степень языка:
- Замыкание Клини: .
Примеры
- — язык состоит из последовательностей нулей, последовательностей единиц и пустой строки.
- — аналогично предыдущему, но не содержит пустую строку.
- — содержит все двоичные векторы и пустую строку.
- Если — язык десятичных представлений всех простых чисел, то язык будет содержать десятичные представления простых чисел, не начинающихся с тройки.
- .