Цепочка: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером {Цепочка}{String, word} {последовательность символов некоторого алфавита <math>\Sigma</...)
 
Нет описания правки
Строка 1: Строка 1:
{Цепочка}{String, word}
'''Цепочка'''([[string]], [[word]]) --- последовательность символов некоторого алфавита <math>\Sigma</math>,
{последовательность символов некоторого алфавита <math>\Sigma</math>,
расположенных один за другим.
расположенных один за другим.


''Длина'' цепочки ---  число символов в ней. Цепочка нулевой
[[Длина цепочки |''Длина'' цепочки]] ---  число символов в ней. Цепочка нулевой
длины называется ''пустой''.
длины называется [[Пустая цепочка|''пустой'']].


Цепочка <math>z=xy</math> называется ''конкатенацией'' (или {\it
Цепочка <math>z=xy</math> называется [[конкатенация|''конкатенацией'']] (или [[сцепление|''сцеплением'']]) цепочек <math>x</math> и <math>y</math>. ''Обращением'' цепочки <math>x</math>
сцеплением}) цепочек <math>x</math> и <math>y</math>. ''Обращением'' цепочки <math>x</math>
называется цепочка <math>x</math>, записанная в обратном порядке. Цепочка
называется цепочка <math>x</math>, записанная в обратном порядке. Цепочка
<math>a^k</math>, называемая <math>k</math>-''кратной конкатенацией'' некоторого
<math>a^k</math>, называемая <math>k</math>-''кратной конкатенацией'' некоторого
Строка 13: Строка 11:
<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>s= xzy</math>.
цепочки <math>w=xy</math>. Цепочка <math>z</math> --- [[подцепочка|''подцепочка'']] цепочки <math>s= xzy</math>.
 
Другие названия --- [[Слово|''Слово'']],[[Строка|''Строка'']].


Другие названия --- ''Слово'',
''Строка''.
}
==Литература==
==Литература==
[Ахо-Ульман],
[Ахо-Ульман],
Строка 25: Строка 22:
[Касьянов-Поттосин],
[Касьянов-Поттосин],


[Касьянов/95],
[Касьянов/95]


[Евстигнеев-Касьянов/94]
[Евстигнеев-Касьянов/94]

Версия от 20:41, 4 июня 2009

Цепочка(string, word) --- последовательность символов некоторого алфавита [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].

Другие названия --- Слово,Строка.

Литература

[Ахо-Ульман],

[Касьянов-Поттосин],

[Касьянов/95]

[Евстигнеев-Касьянов/94]