1. Алфавит, слова, операции над словами

Пусть V={v₁, v₂,…,v_n}, n1 – некоторый алфавит. Тогда любая последовательность x₁x₂…x_k, k0, где x_iV – 1ik , слово в алфавите V, при k=0 –получается пустое слово, обозначим его. Множество всех слов алфавита V обозначается V*.

Слово X =x₁…x_kграфически совпадает со словом Y=y₁…y_l, если x_iV (1ik), y_jV (1jk), l=k, и для любого i ,1ik, x_i=y_i. Будем обозначать графическое совпадение слов X=Y.

Длиной слова Х (обозначается Х) будем называть число вхождений символов в слово Х. Если X =x₁…x_k, тоХ=k .=0

Конкатенацией слов X =x₁…x_k и Y=y₁…y_l называется слово Z= XY= x₁…x_ky₁…y_l. Например, конкатенацией слов «авто» и «бус» будет слово «автобус».

Свойства конкатенации:

 является единицей для конкатенации, т.е. для любого слова Х верно, что Х=Х=Х.

Операция конкатенации является ассоциативной, т.е. (XY)Z=X(YZ).

Операция конкатенации не является коммутативной, XYYX.

Для конкатенации, как и для произведения, конкатенация n одинаковых слов X обозначается Xⁿ. Считаем, что

X⁰=для любого слова Х. Множество V* всех слов алфавита V является полугруппой относительно операции конкатенации.

Полугруппа – множество с заданной на нем ассоциативной бинарной операцией.

Если слово Х=Х₁Х₂, то Х₁начало слова Х, а Х₂– конец слова Х.

Говорят, что слово P входит в слово Q, если существует пара слов R и S, такая, что R – первый элемент пары, S – второй элемент пары, и Q =R P S.

Легко доказать

Утверждение: Если слово P входит в слово Q, то существует некоторое слово U, такое, что P – начало U, а U - конец Q.

Следствие: Если слово P входит в слово Q, то P есть начало некоторого конца Q (или конец некоторого начала Q).

Если P есть некоторое начало (конец) Q и P Q, то P собственное начало (конец) Q.

Конкретные вхождения слова P в слово Q обозначаются RPS, где R, P,S – слова в алфавите V, V. Тогда R – левое крыло вхождения, S – правое крыло вхождения, P - основа.

Говорят, что вхождение P₁ слова P в слово Q предшествует вхождению P₂ слова P в это же слово, если левое крыло вхождения P₁ является собственным началом левого крыла вхождения P₂.

2. Языки. Операции над языками

Произвольное множество цепочек над алфавитом V,иначе любое подмножество свободной полугруппыV*, называется формальным языком надV. Поэтому язык может быть задан теми же способами, как и любое множество:

Перечислением элементов.

Ограничивающим свойством.

Через известные множества

Порождающей процедурой.

В основном будем использовать 4 способ, но начнем с третьего.

Например, для любого Vмножество слов четной длины является языком. Множество слов нечетной длины также явля­ется языком, но в отличие от первого — не замкнутым относи­тельно операции конкатенации. Будем обозначать языки буквойL(с индексами или без них). Рассмотрим операции над языками.

Т.к. язык является множеством, то применимы все соответствующие операции, для которых выполняются все законы теории множеств.

В частности,  L,  L.

Теоретико-множественные операции

Пусть L₁иL₂- два языка над алфавитомV. Язык L называется объединением этих языков(L = L₁ L₂ ), еслиL ={x / x L₁  x L₂}.

Пересечением языков L₁иL₂называется языкL (L = L₁ L₂ ),если L ={x / x L₁ & x L₂}.

Дополнением языка L₁доV*называется языкL (L=V*\L₁),еслиL={ x/ xV* & x L₁}.

Специфические операции

Произведением (иначе конкатенацией) языков L₁иL₂ называется языкL (L=L₁L₂), еслиL={x y/xL₁ & yL₂}.

Например, L₁={ ac, a }, L₂={ cb, b}, тогдаL₁L₂ ={ acb, accb, ab}.

Свойства операции конкатенации:

Операция умножения языков ассоциативна:

L₁ (L₂ L₃)= (L₁ L₂) L₃

Операция умножения языков дистрибутивна от­носительно объединения

L (L₁L₂ ) = LL₁  LL₂.

(L₁L₂ ) L = L₁L  L₂L

Операция умножения языков не коммутативна: L₁ L₂ L₂ L₁.

 L {}= {} L = L

Однако L(L₁L₂ )  LL₁  LL₂ , в общем случае равенства нет, что легко показать, подобрав соответствующий пример.

В силу ассоциативности операции произведения, как и в случае конкатенации цепочек,

записывается как L=L₁ⁿ. По определениюL⁰={}. Отме­тим, что{}   . так как(пустой язык) вообще не со­держит никаких цепочек.

Итерацией языка L₁называется язык L (L=L₁*), если

. Как нетрудно видеть, итерация алфавитаV*(алфавит можно рассматривать как язык, состоящий из односимвольных слов) образует язык, состоящий из всех возможных цепочек, состав­ленных из символовV. Это обстоятельство и объясняет, по­чемуV*используется для обозначения всех слов над алфави­томV.

Вводится также операция усеченной итерации. Lназыва­ется усеченной итерацией языка L₁ (L=L₁⁺), если