Сужение

Протокол (t A) обозначает протокол t, суженный на множество символов A, он строится из t отбрасыванием всех символов, не принадлежащих A.

Пример: <a, b, c, d> <a, b> = <a, b>

Сужение дистрибутивно.

s {} = < >

(s A) B = s (A ∩ B)

Голова и хвост

Если s – непустая последовательность, то обозначим ее первый элемент – s₀, а результат, полученный после его удаления – s’.

Обе операции не определены для пустой последовательности.

s = t ≡ s = t = < > или (s₀ = t₀ & s’ = t’)

4. Звёздочка

Множество A* – набор всех конечных протоколов (включая < >), составленных из элементов множества A. После сужения на A такие протоколы остаются неизменными. Следовательно, определение:

A* = {s: s A = s}

A* = {s: s = < > или (s_o Î A и s’ Î A*)}

Порядок

s ≤ t ≡ u [s^ u = t], будем говорить, что s – префикс t.

Длина

Длина протокола t: #t.

Пример: #<x,y,z> = 3

#< > = 0

#<x> = 1

#<s ^ t> = #(s) + #(t)

Число вхождений в s символов из A вычисляется выражением #(t A)

Число вхождений символа x в протокол s определяется так:

s ↓ x = #(s {x})