Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками — различия между версиями
Строка 39: | Строка 39: | ||
2) | 2) | ||
''Дополнение языка'' | ''Дополнение языка'' | ||
− | <tex> \setminus L</tex>=<tex>L \ | + | <tex> \setminus L</tex>=<tex>L \varepsilon^* \setminus L</tex> |
3) | 3) | ||
Строка 53: | Строка 53: | ||
''Замыкание Клини'' | ''Замыкание Клини'' | ||
<tex>L^*=\bigcup_{i=0}^{\infty}L^i</tex> | <tex>L^*=\bigcup_{i=0}^{\infty}L^i</tex> | ||
− | <tex>L^i=LL^ | + | <tex>L^i=LL^{i-1}</tex> |
<tex>L^1=L</tex> | <tex>L^1=L</tex> | ||
− | <tex>L^0={\ | + | <tex>L^0={\varepsilon}</tex> |
'''Пример''': | '''Пример''': | ||
<tex>L={a,ab}</tex> | <tex>L={a,ab}</tex> | ||
− | <tex>L^*={\ | + | <tex>L^*={\varepsilon,a,ab,aa,aab,aba,abab,...}</tex> |
Версия 07:43, 4 октября 2010
Алфавит и Слово
Алфавит - конечное непустое множество символов. Условимся обозначать алфавиты символом
.Слово, или цепочка - это конечная последовательность символов некоторого алфавита. Например, 01101 - это цепочка в бинарном алфавите
. Цепочка 111 это тоже цепочка в этом алфавите. Пустая цепочка - это цепочка, не содержащая ни одного символа. Эту цепочку обозначаемую , можно рассматривать как цепочку в любом алфавите. Длина цепочки - число позиций для символов в цепочке. Степени алфавита Если - некоторый алфавит, то можно выразить множество всех цепочек определенной длины, состоящих из символов данного алфавита, используя знак степени. Определим , как множество всех цепочек длины k, состоящих из символов алфавита .Конкатенация слов Пусть x и y - цепочки. Тогда xy обозначает их конкатенацию (соединение), т.е. цепочку, в которой последовательно записаны цепочки x и y.
Свойства
- Ассоциотивность
- нейтральный элемент
Таким образом мы получаемсвободный моноид слов.
Слово
является префиксом , если для некоторого .Слово
является суффиксом , если для некоторого .Слово
является подстрокой , если для некоторого .(\gamma, \delta могут быть пустыми)
Язык
Язык - множество строчек, каждая из которых принадлежит
, где - некоторый фиксированный алфавит. Если - алфавит, и , то - это язык над , или в . Отметим, что язык в не обязательно должен содержать цепочка, в которые входят все символы . Поэтому, если известно, что является языком в , то можно утверждать, что - это язык над любым алфавитом, содержащим .Операции над языками 1)
- - объединение
- - пересечение
- - разность
2) Дополнение языка
=3) Конкатенация
Если язык состоит из одного слова , то для упрощения записи его можно обозначить, как \alpha. Тогда можно определить L\alpha и L\eps4) Конкатенация с обратным словом
5) Замыкание Клини
Пример: