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