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

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


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

Версия от 19:31, 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.