4624
правки
Цепочка: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KVN (обсуждение | вклад) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Цепочка'''([[string]], [[word]]) | '''Цепочка'''([[string]], [[word]]) — последовательность символов некоторого алфавита <math>\Sigma</math>, | ||
расположенных один за другим. | расположенных один за другим. | ||
[[Длина цепочки |''Длина'' цепочки]] | [[Длина цепочки |''Длина'' цепочки]] — число символов в ней. Цепочка нулевой | ||
длины называется [[Пустая цепочка|''пустой'']]. | длины называется [[Пустая цепочка|''пустой'']]. | ||
| Строка 8: | Строка 8: | ||
называется цепочка <math>x</math>, записанная в обратном порядке. Цепочка | называется цепочка <math>x</math>, записанная в обратном порядке. Цепочка | ||
<math>a^k</math>, называемая <math>k</math>-''кратной конкатенацией'' некоторого | <math>a^k</math>, называемая <math>k</math>-''кратной конкатенацией'' некоторого | ||
символа <math>a</math>, определяется по правилам: <math>a^0</math> | символа <math>a</math>, определяется по правилам: <math>a^0</math> — пустая цепочка, | ||
<math>a^k=a a^{k-1}</math> для любого <math>k>0</math>. | <math>a^k=a a^{k-1}</math> для любого <math>k>0</math>. | ||
Цепочка <math>x</math> называется [[префикс|''префиксом'']], | Цепочка <math>x</math> называется [[префикс|''префиксом'']], | ||
а цепочка <math>y</math> | а цепочка <math>y</math> — [[суффикс|''суффиксом'']] | ||
цепочки <math>w=xy</math>. Цепочка <math>z</math> | цепочки <math>w=xy</math>. Цепочка <math>z</math> — [[подцепочка|''подцепочка'']] цепочки <math>s= xzy</math>. | ||
Другие названия | Другие названия — [[Слово|''Слово'']],[[Строка|''Строка'']]. | ||
==Литература== | ==Литература== | ||
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2. | |||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | |||
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986. | |||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||