Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками — различия между версиями
(→Примеры) |
м |
||
Строка 36: | Строка 36: | ||
|id = deflanguage | |id = deflanguage | ||
|definition = | |definition = | ||
− | '''Язык''' над алфавитом <tex>\Sigma</tex> {{---}} некоторое подмножество <tex>\Sigma^*</tex>. Иногда такие | + | '''Язык''' над алфавитом <tex>\Sigma</tex> {{---}} некоторое подмножество <tex>\Sigma^*</tex>. Иногда такие языки называют '''формальными''', чтобы подчеркнуть отличие от языков в привычном смысле. |
}} | }} | ||
Версия 19:54, 23 января 2012
Определение: |
Алфавит — конечное непустое множество. Условимся обозначать алфавит символом | .
Наиболее часто используются следующие алфавиты:
- — бинарный или двоичный алфавит.
- — множество строчных букв английского алфавита.
Определение: |
Слово (цепочка) — конечная последовательность символов некоторого алфавита. |
Определение: |
Пустая цепочка — цепочка, не содержащая ни одного символа. Эту цепочку, обозначаемую | , можно рассматривать как цепочку в любом алфавите.
Определение: |
Длина цепочки — число символов в цепочке. Длину некоторой цепочки | обычно обозначают .
Определение: |
— множество цепочек длины над алфавитом . |
Определение: |
— множество всех цепочек над алфавитом . |
Определение: |
Язык над алфавитом | — некоторое подмножество . Иногда такие языки называют формальными, чтобы подчеркнуть отличие от языков в привычном смысле.
Отметим, что язык в не обязательно должен содержать цепочки, в которые входят все символы . Поэтому, если известно, что является языком над , то можно утверждать, что — это язык над любым алфавитом, являющимся надмножеством .
Определение: |
Пусть | . Тогда обозначает их конкатенацию, т.е. цепочку, в которой последовательно записаны цепочки x и y.
Свойства
Таким образом, мы получаем свободный моноид слов.
Операции над языками
Пусть
и — языки. Тогда над ними можно определить следующие операции.- Теоретико-множественные операции:
- — объединение,
- — пересечение,
- — разность,
- — дополнение.
- Конкатенация: .
- Конкатенация с обратным языком: ; конкатенация с обратным словом: .
- Степень языка:
- Замыкание Клини: .
Примеры
- — язык состоит из последовательностей нулей, последовательностей единиц и пустой строки.
- — аналогично предыдущему, но не содержит пустую строку.
- — содержит все двоичные векторы и пустую строку.
- Если — язык десятичных представлений всех простых чисел, то язык будет содержать десятичные представления простых чисел, не начинающихся с тройки.
- .