Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками — различия между версиями
| Строка 1: | Строка 1: | ||
| − | {{Определение | + | {{Определение алфавита |
|definition = | |definition = | ||
'''Алфавит''' - конечное непустое множество символов. Условимся обозначать алфавиты символом <tex>\Sigma</tex>. | '''Алфавит''' - конечное непустое множество символов. Условимся обозначать алфавиты символом <tex>\Sigma</tex>. | ||
}} | }} | ||
| + | |||
| + | {{Определение слова | ||
| + | |definition = | ||
'''Слово''', или '''цепочка''' - это конечная последовательность символов некоторого алфавита. Например, 01101 - это цепочка в бинарном алфавите <tex>\Sigma = {0,1}</tex>. Цепочка 111 это тоже цепочка в этом алфавите. | '''Слово''', или '''цепочка''' - это конечная последовательность символов некоторого алфавита. Например, 01101 - это цепочка в бинарном алфавите <tex>\Sigma = {0,1}</tex>. Цепочка 111 это тоже цепочка в этом алфавите. | ||
| + | }} | ||
| + | |||
''Пустая цепочка'' - это цепочка, не содержащая ни одного символа. Эту цепочку обозначаемую <tex> \varepsilon </tex>, можно рассматривать как цепочку в любом алфавите. | ''Пустая цепочка'' - это цепочка, не содержащая ни одного символа. Эту цепочку обозначаемую <tex> \varepsilon </tex>, можно рассматривать как цепочку в любом алфавите. | ||
''Длина цепочки'' - число символов в цепочке. | ''Длина цепочки'' - число символов в цепочке. | ||
| + | {{Определение степени алфавита | ||
| + | |definition = | ||
'''Степени алфавита''' | '''Степени алфавита''' | ||
Если <tex>\Sigma</tex> - некоторый алфавит, то можно выразить множество всех цепочек определенной длины, состоящих из символов данного алфавита, используя знак степени. Определим <tex>\Sigma^k</tex>, как множество всех цепочек длины <tex>k</tex>, состоящих из символов алфавита <tex>\Sigma</tex>. Определим <tex>\Sigma^*</tex>, как <tex>\Sigma^*=\left\{\Sigma^0, \Sigma^1, \Sigma^2, ...\right\}</tex> | Если <tex>\Sigma</tex> - некоторый алфавит, то можно выразить множество всех цепочек определенной длины, состоящих из символов данного алфавита, используя знак степени. Определим <tex>\Sigma^k</tex>, как множество всех цепочек длины <tex>k</tex>, состоящих из символов алфавита <tex>\Sigma</tex>. Определим <tex>\Sigma^*</tex>, как <tex>\Sigma^*=\left\{\Sigma^0, \Sigma^1, \Sigma^2, ...\right\}</tex> | ||
| + | }} | ||
| + | {{Конкатенация | ||
| + | |definition = | ||
'''Конкатенация слов''' | '''Конкатенация слов''' | ||
Пусть <tex>x</tex> и <tex>y</tex> - цепочки. Тогда <tex>xy</tex> обозначает их ''конкатенацию'' (соединение), т.е. цепочку, в которой последовательно записаны цепочки x и y. | Пусть <tex>x</tex> и <tex>y</tex> - цепочки. Тогда <tex>xy</tex> обозначает их ''конкатенацию'' (соединение), т.е. цепочку, в которой последовательно записаны цепочки x и y. | ||
| + | }} | ||
''Свойства'' | ''Свойства'' | ||
Версия 01:51, 8 октября 2010
Пустая цепочка - это цепочка, не содержащая ни одного символа. Эту цепочку обозначаемую , можно рассматривать как цепочку в любом алфавите. Длина цепочки - число символов в цепочке.
Шаблон:Определение степени алфавита
Свойства
- Ассоциотивность
- нейтральный элемент
Таким образом мы получаемсвободный моноид слов.
Слово является префиксом , если для некоторого .
Слово является суффиксом , если для некоторого .
Слово является подстрокой , если для некоторого , .
(, могут быть пустыми)
Если - алфавит, и , то - это язык над , или в . Отметим, что язык в не обязательно должен содержать цепочки, в которые входят все символы . Поэтому, если известно, что является языком в , то можно утверждать, что - это язык над любым алфавитом, содержащим .
