Языки

Любой язык основан на использовании определенного алфавита. Алфавит – это конечное непустое множество символов

Σ= {a1, a2, a3, ... , an}, n>0. Строка – упорядоченная конечная последовательность символов алфавита Σ. Для обозначения строк будем использовать строчные буквы греческого алфавита α, β, γ, ...

Например, α = aabb означает, что строка, обозначаемая буквой α, представляет собой последовательность из четырех символов aabb.

Конкатенация двух строк α и β – это бинарная операция, результат которой есть строка αβ, полученная приписыванием к стро-

ке α справа строки β, т.е. если α = a1 a2 a3 ... an , β = b1 b2 b3 ... bm , то

αβ = a1 a2 a3 ... an b1 b2 b3 ... bm .

Очевидно, что конкатенация является ассоциативной, но некоммутативной операцией, т.е. для любых строк α, β, γ в алфавите Σ

справедливо равенство α(βγ) = (αβ)γ, но неверно, что для любых α, β αβ = βα. Например, если α = ab, β = ba, то αβ = abba, а βα = baab,

т.е. αβ ≠ βα.

Операция обращения строки α обозначается α-1 и дает строку, полученную из α выписыванием всех входящих в нее символов в

обратном порядке, т.е. если α = a1 a2 a3 ... an , то α-1 = an an -1 ... a2 a1 . Нетрудно видеть, что для любых строк α и β верно соотношение (αβ)-1 = β-1α-1.

Длина строки α обозначается |α| и равна числу символов (с учетом повторений) в этой строке. Так, если α = a1a2a3 ... an, то |α| = n, n ≥ 0.

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

α = βγδ, где |β| ≥ 0, |γ| ≥0, |δ| ≥ 0.

Тогда строка β называется префиксом строки α, строка δ – ее суффиксом, а δ – ее подстрокой. Отсюда, в частности, следует, что пустая подстрока ε является подстрокой любой строки α.

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

Введем полезное обозначение для результата конкатенации строки α с самой собой: αα = α2, ααα = α3 и т.д.

В общем виде эту операцию над строкой α можно определить рекурсивно: α0 = ε, αn+1 = αnα, n ≥ 0. В частности, если α = aa ... a и |

α| = n, то α = аn.

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

Пример 1.1.

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

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

Пример 1.2.

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

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

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

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

есть множество L = Σ* \ L.

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

L1L2 = {αβ | α L1, β L2},

состоящий из всевозможных конкатенаций строк α языка L1 и строк β языка L2, образованных в указанном порядке.

Нетрудно заметить, что операция сцепления двух языков ассоциативна, но не коммутативна, т.е. для любых языков L1, L2, L3 из Σ*

(L1L2)L3 = L1(L2L3),

но существует пара языков L1, L2 такая, что L1L2 ≠ L2L1.

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

L0 = {ε}, L1 = L, L2 = LL, L3 = LLL, ...

В общем виде операцию Ln (n ≥ 0) можно определить рекурсивно следующим образом: L0 = {ε}, Ln+1 = LnL, n ≥ 0.

Пример 1.3.

Если L = {anbn | n ≥ 0}, то L2 = {anbnambm| n ≥ 0, m ≥ 0}.

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

Σ0 = {ε} = {α | α Σ* & |α| = 0}, Σ1 = Σ = {α | α Σ* & |α| = 1},

Σ2 = {a1a2 | a1 Σ, a2 Σ} = {α | α Σ* & |α| = 2},

и т.д.

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

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

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

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

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