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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 25: Строка 25:


[Евстигнеев-Касьянов/94]
[Евстигнеев-Касьянов/94]
[[Категория: Теория формальных языков]]

Версия от 20:43, 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]