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

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Цепочка'''([[string]], [[word]]) --- последовательность символов некоторого алфавита <math>\Sigma</math>,
'''Цепочка'''([[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>s= xzy</math>.
цепочки <math>w=xy</math>. Цепочка <math>z</math> [[подцепочка|''подцепочка'']] цепочки <math>s= xzy</math>.


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


==Литература==
==Литература==
[Ахо-Ульман],
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.


[Касьянов-Поттосин],
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.


[Касьянов/95]
* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.
 
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.


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


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

Навигация