Материал из Викиконспекты
|
|
| (не показаны 73 промежуточные версии 7 участников) |
| Строка 1: |
Строка 1: |
| − | ==Алфавит и Слово==
| + | #перенаправление [[Основные определения, связанные со строками]] |
| − | | |
| − | | |
| − | '''Алфавит''' - конечное непустое множество символов. Условимся обозначать алфавиты символом <tex>\Sigma</tex>.
| |
| − |
| |
| − | '''Слово''', или '''цепочка''' - это конечная последовательность символов некоторого алфавита. Например, 01101 - это цепочка в бинарном алфавите <tex>\Sigma = {0,1}</tex>. Цепочка 111 это тоже цепочка в этом алфавите.
| |
| − | ''Пустая цепочка'' - это цепочка, не содержащая ни одного символа. Эту цепочку обозначаемую <tex> \varepsilon </tex>, можно рассматривать как цепочку в любом алфавите.
| |
| − | ''Длина цепочки'' - число позиций для символов в цепочке.
| |
| − | '''Степени алфавита'''
| |
| − | Если <tex>\Sigma</tex> - некоторый алфавит, то можно выразить множество всех цепочек определенной длины, состоящих из символов данного алфавита, используя знак степени. Определим <tex>\Sigma^k</tex>, как множество всех цепочек длины k, состоящих из символов алфавита <tex>\Sigma</tex>.
| |
| − | | |
| − | | |
| − | '''Язык''' - множество строчек, каждая из которых принадлежит <tex>\Sigma^*</tex>, где <tex>\Sigma</tex> - некоторый фиксированный алфавит. Если <tex>\Sigma</tex> - алфавит, и <tex>\L \subseteq Sigma^*</tex>
| |
| − | '''Конкатенация'''
| |
| − | '''Свободный моноид слов'''
| |
Текущая версия на 23:10, 12 июня 2014
