Редактирование: Основные определения, связанные со строками

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 5: Строка 5:
  
 
{{Определение
 
{{Определение
|id=alphabet
 
 
|definition =
 
|definition =
 
'''Алфавит''' (англ. ''alphabet'') {{---}} конечное непустое [[Множества|множество]] символов. Условимся обозначать алфавит большой греческой буквой <tex>\Sigma</tex>.
 
'''Алфавит''' (англ. ''alphabet'') {{---}} конечное непустое [[Множества|множество]] символов. Условимся обозначать алфавит большой греческой буквой <tex>\Sigma</tex>.
Строка 12: Строка 11:
 
Наиболее часто используются следующие алфавиты:
 
Наиболее часто используются следующие алфавиты:
 
* <tex>\Sigma=\{0, 1\}</tex> {{---}} бинарный или двоичный алфавит.
 
* <tex>\Sigma=\{0, 1\}</tex> {{---}} бинарный или двоичный алфавит.
* <tex>\Sigma=\{a, b, \dots,z\}</tex> {{---}} множество строчных букв английского алфавита.
+
* <tex>\Sigma=\{a, b, ...,z\}</tex> {{---}} множество строчных букв английского алфавита.
 
* <tex>\Sigma = \left\{0, 1, 2, \dots, 9\right\} </tex> {{---}} алфавит цифр.
 
* <tex>\Sigma = \left\{0, 1, 2, \dots, 9\right\} </tex> {{---}} алфавит цифр.
 
* <tex>\Sigma = \left\{\cdot, -\right\} </tex> {{---}} алфавит, лежащий в основе азбуки Морзе.
 
* <tex>\Sigma = \left\{\cdot, -\right\} </tex> {{---}} алфавит, лежащий в основе азбуки Морзе.
Строка 18: Строка 17:
  
 
{{Определение
 
{{Определение
|id=string
 
 
|definition =
 
|definition =
 
'''Слово''' (англ. ''string'') или '''цепочка''' {{---}} конечная последовательность символов некоторого алфавита.
 
'''Слово''' (англ. ''string'') или '''цепочка''' {{---}} конечная последовательность символов некоторого алфавита.
Строка 69: Строка 67:
 
{{Определение
 
{{Определение
 
|id=border
 
|id=border
|definition='''Бордер''' (англ. ''circumfix'') строки <tex>\beta</tex> {{---}} строка <tex>\alpha : \beta = \gamma \alpha = \alpha \eta</tex>.
+
|definition='''Бордер''' (англ. ''circumfix'') строки <tex>\beta</tex> {{---}} строка <tex>\alpha : \beta = \gamma \alpha = \alpha \eta = \alpha \mu \alpha</tex>.
 
}}
 
}}
  
Строка 92: Строка 90:
 
{{Утверждение
 
{{Утверждение
 
|statement=Пусть известна строка <tex>\tau</tex> {{---}} период <tex>\alpha</tex> и <tex>|\alpha|</tex>, тогда можно восстановить всю строку <tex>\alpha</tex>.
 
|statement=Пусть известна строка <tex>\tau</tex> {{---}} период <tex>\alpha</tex> и <tex>|\alpha|</tex>, тогда можно восстановить всю строку <tex>\alpha</tex>.
|proof=Из определения периода строки следует, что <tex>\alpha[1 \dots |\tau|] = \alpha[|\tau| + 1 \dots 2 \cdot |\tau|] = \dots = \alpha[|\tau| \cdot (k - 1) + 1 \dots |\tau| \cdot k] </tex>, где <tex>k = </tex> <tex dpi="140">\left\lfloor\frac{|\alpha|}{|\tau|} \right\rfloor</tex>.  
+
|proof=Из определения периода строки следует, что <tex>\alpha[1 \dots |\tau|] = \alpha[|\tau| + 1 \dots 2 \cdot |\tau|] = \dots = \alpha[|\tau| \cdot (k - 1) + 1 \dots |\tau| \cdot k] </tex>, где <tex>k = </tex> <tex dpi="140">\lfloor\frac{|\alpha|}{|\tau|} \rfloor</tex>.  
  
Таким образом <tex>\alpha = </tex><tex dpi="140">\sum \limits_{i=1}^{\left\lfloor\frac{|\alpha|}{|\tau|} \right\rfloor}</tex><tex> \tau + \tau[1 \dots |\alpha| \bmod |\tau|]</tex>.
+
Таким образом <tex>\alpha = </tex><tex dpi="140">\sum \limits_{i=1}^{\lfloor\frac{|\alpha|}{|\tau|} \rfloor}</tex><tex> \tau + \tau[1 \dots |\alpha| \bmod |\tau|]</tex>.
 
}}
 
}}
  
Строка 111: Строка 109:
  
 
Пусть <tex>\beta = abr\underline{aca}dabra</tex>, тогда <tex>\alpha = aca</tex> {{---}} подстрока строки <tex>\beta</tex>.
 
Пусть <tex>\beta = abr\underline{aca}dabra</tex>, тогда <tex>\alpha = aca</tex> {{---}} подстрока строки <tex>\beta</tex>.
 
{{Определение
 
|id=repetition
 
|definition='''Тандемным повтором''' (англ. ''repetition'') называется непустая строка вида <math>\alpha\alpha</math>.
 
}}
 
 
{{Определение
 
|id=palindrome
 
|definition='''Палиндромом''' (англ. <i>Palindrome</i>) называется строка вида <tex>\alpha\overline{\alpha}</tex> или <tex>\alpha c\overline{\alpha}</tex>, где <tex>\overline{\alpha}</tex> {{---}} развернутая строка <tex>\alpha</tex>, <tex>c</tex> {{---}} любой символ.
 
}}
 
  
 
{{Определение
 
{{Определение
Строка 129: Строка 117:
 
''или''
 
''или''
  
2. <tex> \mathcal \exists k : k \leqslant \min(|\alpha|, |\beta|) </tex> и <tex> \alpha[k] < \beta[k] </tex>, при этом <tex> \mathcal \forall j < k : \alpha_j = \beta_j </tex>
+
2. <tex> \mathcal {9} k : k \leqslant \min(|\alpha|, |\beta|) </tex> и <tex> \alpha[k] < \beta[k] </tex>, при этом <tex> \mathcal {8} j < k : \alpha_j = \beta_j </tex>
 
}}
 
}}
  
Строка 164: Строка 152:
 
* <tex>(\{0\}\{0\}^*) \cup (\{1\}\{1\}^*)</tex> {{---}} аналогично предыдущему, но не содержит пустую строку.
 
* <tex>(\{0\}\{0\}^*) \cup (\{1\}\{1\}^*)</tex> {{---}} аналогично предыдущему, но не содержит пустую строку.
 
* <tex>(\{0\} \cup \{1\})^* = \{0, 1\}^*</tex> {{---}} содержит все двоичные векторы и пустую строку.
 
* <tex>(\{0\} \cup \{1\})^* = \{0, 1\}^*</tex> {{---}} содержит все двоичные векторы и пустую строку.
* Если <tex>L_p</tex> — язык десятичных представлений всех простых чисел, то язык <tex>(L_p \setminus (\{3\}\{1,2,3,4,5,6,7,8,9,0\}^*)) \ \ </tex> будет содержать десятичные представления простых чисел, не начинающихся с тройки.
+
* Если <tex>L_p</tex> — язык десятичных представлений всех простых чисел, то язык <tex>(L_p \setminus (\{3\}\{1,2,3,4,5,6,7,8,9,0\}^*))</tex> будет содержать десятичные представления простых чисел, не начинающихся с тройки.
 
* <tex>\{\mathrm{ab, ba, bba, abab, aa}\}a^{-1} = \{\mathrm{b, bb, a}\}</tex>.
 
* <tex>\{\mathrm{ab, ba, bba, abab, aa}\}a^{-1} = \{\mathrm{b, bb, a}\}</tex>.
  

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)