Лекция 1 Языки и грамматики Языки

любой язык основан на использовании определенного алфа-вита. Алфавит – это конечное непустое множество символов S = {a₁, a₂, a₃, ... , a_n}, n > 0. Строка – упорядоченная конечная последовательность символов алфавита S. Для обозначения строк будем использовать строчные буквы греческого алфавита a, b, g, ... Например, a = aabb означает, что строка, обозначаемая буквой a, представляет собой последовательность из четырех символов aabb.

Конкатенация двух строк a и b – это бинарная операция, ре-зультат которой есть строка ab, полученная приписыванием к стро-ке a справа строки b, т.е. если a = a₁ a₂ a₃ ... a_n , b = b₁ b₂ b₃ ... b_m , то ab = a₁ a₂ a₃ ... a_n b₁ b₂ b₃ ... b_m .

Очевидно, что конкатенация является ассоциативной, но не-коммутативной операцией, т.е. для любых строк a, b, g в алфавите S справедливо равенство a(bg) = (ab)g, но неверно, что для любых a, b ab = ba. Например, если a = ab, b = ba, то ab = abba, а ba = baab, т.е. ab ¹ ba.

Операция обращения строки a обозначается a^-1 и дает строку, полученную из a выписыванием всех входящих в нее символов в обратном порядке, т.е. если a = a₁ a₂ a₃ ... a_n , то a^-1 = a_n a_{n -1} ... a₂ a₁ . Нетрудно видеть, что для любых строк a и b верно соотношение (ab)^-1 = b^-1a^-1.

Длина строки a обозначается |a| и равна числу символов (с учетом повторений) в этой строке. Так, если a = a₁a₂a₃ ... a_n, то |a| = n, n ³ 0.

Пустой строкой называется строка e, для которой |e| = 0. Очевидно, что для любой строки a ea = ae = a, т.е. строка e является нейтральным элементом относительно конкатенации. В разных ситуациях бывает необходимо рассматривать структуру строки a, т.е. выделять в ней отдельные части, которые сами являются строками. Пусть

a = bgd, где |b| ³ 0, |g| ³ 0, |d| ³ 0.

Тогда строка b называется префиксом строки a, строка d – ее суффиксом, а g – ее подстрокой. Отсюда, в частности, следует, что пустая подстрока e является подстрокой любой строки a.

Длина строки связана с операцией конкатенации простым соотношением: |ab| = |a| + |b|.

Введем полезное обозначение для результата конкатенации строки a с самой собой: aa = a², aaa = a³ и т.д.

В общем виде эту операцию над строкой a можно определить рекурсивно: a⁰ = e, aⁿ⁺¹ = aⁿa, n ³ 0. В частности, если a = aa ... a и |a| = n, то a = аⁿ.

Теперь введем одно из основных понятий информатики – понятие формального языка. Формальным языком называется любое множество строк (в данном алфавите S).

Пример 1.1.

Пусть S = {a, b}. Тогда множество L = {a, b, aa, bb, ab, aab} является (конечным) формальным языком в алфавите S.

В дальнейшем в этом курсе лекций слово «язык» будет обозначать формальный язык в некотором заранее фиксированном алфавите.

Пример 1.2.

Множество L = {aⁿbⁿ| n ³ 0} является (бесконечным) языком в алфавите S = {a, b}. Его элементами являются строки вида ab, aabb, aaabbb, ... , в том числе пустая строка e.

Заметим, что не следует путать пустой язык L = Æ, не содержащий ни одной строки, и язык L = {e}, состоящий из единственной (пустой) строки e.

Язык, состоящий из всех строк в алфавите S, обозначается S*. Если L – язык в алфавите S, то, очевидно, L Í S*.

Так как языки – это множества (строк), то над ними можно совершать обычные теоретико-множественные операции объеди-нения È, пересечения Ç, разности \ и образования дополнения (по отношению к S*), т.е. если L – язык в алфавите S, то его дополнение есть множество = S* \ L.

Наряду с этими операциями над языками можно определить еще ряд специфических операций. Пусть L₁, L₂ – языки в алфавите S, тогда их сцепление – это язык

L₁L₂ = {ab | a Î L₁, b Î L₂},

состоящий из всевозможных конкатенаций строк a языка L₁ и строк b языка L₂, образованных в указанном порядке.

Нетрудно заметить, что операция сцепления двух языков ассо-циативна, но не коммутативна, т.е. для любых языков L₁, L₂, L₃ из S*

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

но существует пара языков L₁, L₂ такая, что L₁L₂ ¹ L₂L₁.

Определим еще одну операцию – итерацию языка L:

L⁰ = {e}, L¹ = L, L² = LL, L³ = LLL, ...

В общем виде операцию Lⁿ (n ³ 0) можно определить рекурсивно следующим образом: L⁰ = {e}, Lⁿ⁺¹ = LⁿL, n ³ 0.

Пример 1.3.

Если L = {aⁿbⁿ | n ³ 0}, то L² = {aⁿbⁿa^mb^m| n ³ 0, m ³ 0}.

Полезно отметить, что если итерировать алфавит S, который сам, в свою очередь, является (конечным) языком, все строки которого имеют длину 1, то последовательно будем иметь:

S⁰ = {e} = {a | a Î S* & |a| = 0},

S¹ = S = {a | a Î S* & |a| = 1},

S² = {a₁a₂ | a₁ Î S, a₂ Î S} = {a | a Î S* & |a| = 2},

и т.д.

В общем случае, Sⁿ = {a | a Î S* и |a| = n}, n ³ 0, т.е. Sⁿ – это множество всех строк длины n в алфавите S.

В заключение этого раздела введем еще одну очень важную операцию над языками – так называемое замыкание Клини (или звездочка), которая определяется следующим образом. Пусть L – произвольный язык, тогда

L* = L⁰ È L¹ È L² È ... = Lⁱ.

Для удобства, чтобы отделить пустую строку e, которая всегда принадлежит L*, иногда используется позитивное замыкание языка L, обозначаемое L⁺:

L⁺ = Lⁱ = L¹ È L² È ... .

Из определения следует, что L* = {e} È L⁺.

Заметим, что ранее введенное обозначение языка S* вполне согласуется с только что введенной операцией замыкания: объединение S⁰ È S¹ È S² È ... как раз и представляет собой множество всех строк в алфавите S (включая пустую строку).