Стр. 9 - Информационные структуры и их преобразование

Содержание 7
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
1.1. Элементы теории языка и их грамматика. Символы, цепочки и
операции над ними
Языком в алфавите Σ называют множество цепочек, состоящих из
элементов этого алфавита.
Алфавит-любое множество символов.
В общем случае алфавит не обязан быть конечным, но мы будем иметь
дело только с конечным.
Цепочка - последовательность символов алфавита.
Цепочка и слово - синонимы.
Символы: a,b,c,d - элементы алфавита,
M,Q,S,T - переменные, обозначающие любой символ алфавита,
u, w, v, x, y, z, t - обозначают цепочки символов. u=аbc.
Причем сцепление цепочек xy≠yx (сон ≠ нос).
Пример: U=abcd - цепочка,
X=cb - цепочка.
λх=хλ=х, где λ - пустая цепочка - цепочка, не содержащая ни одного
символа (обозначается λ или е).
Цепочка, содержащая i одинаковых символов – ai= aa…a (i штук).|ai |=i.
Если x=ab и y=cd, то w=xy=abcd называется конкатенацией цепочек
x и y.
Обращение цепочки x обозначается xr .Если x=abc, то xr=cba.
Пусть x,y,z – произвольные цепочки в Σ .И пусть имеется цепочка
w=xyz.
Цепочку x называют префиксом, цепочку z-суффиксом цепочки w,
цепочка y-инфикс цепочки w.
Пусть имеется цепочка x=s…, s-голова цепочки, x=…s, s – хвост
цепочки x.
Если A={a,b},B={c,d}-2 алфавита, то множество AB={ac,bc,ad,bd} и
других комбинаций быть не может. Коммутативный закон здесь не
приемлем.
Пусть L1 -язык в алфавите Σ 1,а L2-язык в алфавите Σ2 .Тогда язык L1 L2 –
конкатенация языков.
Сцепление произвольного числа цепочек языка L охватывается
понятием итерация и обозначается L∗ =L0 ∪L1 ∪…, L0=λ, L+ - усечённая
итерация. L∗\L +=λ. Пусть Σ 1 и Σ 2-алфавиты. Гомоморфизмом называют
любое отображение h=Σ ∗
1 →Σ2
∗ .
Пример : Σ1 ={a,b},Σ2={0,1}.Тогда h(a)=1,h(b)=0.