Цепочка

Материал из WikiGrapp
Перейти к:навигация, поиск

Цепочка(string, word) — последовательность символов некоторого алфавита \Sigma, расположенных один за другим.

Длина цепочки — число символов в ней. Цепочка нулевой длины называется пустой.

Цепочка z=xy называется конкатенацией (или сцеплением) цепочек x и y. Обращением цепочки x называется цепочка x, записанная в обратном порядке. Цепочка a^k, называемая k-кратной конкатенацией некоторого символа a, определяется по правилам: a^0 — пустая цепочка, a^k=a a^{k-1} для любого k>0.

Цепочка x называется префиксом, а цепочка yсуффиксом цепочки w=xy. Цепочка zподцепочка цепочки s= xzy.

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

Литература

  • Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.
  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.
  • Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.