Алфавит, слово, язык

Рассмотрим самое простое понятие теории языков - понятие алфавита.

Алфавит - это произвольное непустое конечное множество V = {а₁, ... , a_n}, элементы которого называют буквами или символами.

Обычно задают определенную нумерацию алфавита (как, скажем, для русского алфавита: "а" - первая буква, "б" - вторая и т.д. до 33-й - "я"). Впредь договоримся, фиксируя алфавит, записывать его буквы в порядке их номеров.

*От древнегреческих "pragma" - "дело, действие" и "pragmateia" - "деятельность".

Определение 7.1. Словом или цепочкой в алфавите V называют произвольный кортеж из множества V^k (k-й декартовой степени алфавита V) для различных k = 0, 1, 2, ...

Например, если V = {а, b, с}, то (а), (b), (с), (а, b), (а, b, с), (с, b, а, а, с) и т.д. есть слова в V.

При k = 0 получаем пустой кортеж, называемый в данном контексте пустым словом или пустой цепочкой и обозначаемый λ. Множество всех слов в алфавите V обозначают V*, а множество всех непустых слов в V - как V⁺. Слова, ради удобства чтения и простоты записи, будем записывать без скобок и запятых (ер. с записями кортежей в 1.2). Так, для записанных выше слов получим: а, b, с, аb, аbс, сbаас.

Такая запись слова согласуется с его интуитивным пониманием как цепочки следующих друг за другом символов. Тогда пустое слово - это слово, не имеющее символов, "пустой лист бумаги", на котором еще ничего не написано.

По определению, длина слова w - число компонент кортежа, т.е. если w ∈ V^r, то длина слова w равна r. Длину слова w договоримся обозначать |w|. Ясно, что для пустого слова |λ| = 0. Длину слова тем самым можно понимать как число составляющих это слово букв.

Докажем, что множество V* счетно. Для этого достаточно построить какую-либо нумерацию этого множества. Рассмотрим здесь нумерацию, называемую лексикографической. В данной нумерации пустому слову присваивается номер 0, а буквам а₁, ... , a_n алфавита V - номера 1, ... , n соответственно. Если слово х имеет лексикографический номер L_x , то слову xa_i присваивается номер nl_x + i. Отсюда следует, что лексикографический номер слова a_i1a_i2 ... a_ik будет равен

n^k-1i₁ + n^k-2i₂ +...+i_k.

Заметим, что последняя сумма напоминает запись числа в системе счисления по модулю n (мощности алфавита) с тем лишь различием, что используется цифра n, но не допускается цифра 0. Итак, по любому слову в алфавите V однозначно вычисляется его лексикографический номер. Обратно, любое натуральное число однозначно раскладывается по степеням n указанным выше образом.

Действительно, если дано число N, то при 0 ≤ N ≤ n оно служит номером пустого слова (N = 0) или некоторой буквы алфавита. Иначе представим N в виде

N = k₁n + r₀,

где 1 ≤ r₀ ≤ n .

Если k₁ ≤ n, то N есть номер слова a_k1 a_r0. Иначе раскладываем k₁ в виде

k₁ = k₂n + r₁,

где 1 ≤ r₁ ≤ n. Тогда

N = k₂n² + r₁n + r₀.

С числом k₂ поступаем точно так же, как и с k₁. После конечного числа шагов получим разложение числа N в виде

N = n^m r_m + n^m-1r_m-1 +...+ nr₁ + r₀,

где каждое число r_i (0 ≤ i ≤ m) находится в диапазоне от 1 до n. По полученному разложению N однозначно восстанавливается слово в V, имеющее номер N:

Пример 7.1. Вычислим номер слова сbаас в алфавите {а, b, с}. Имеем

3⁴ · 3 + 3³ · 2 + 3² · 1 + 3¹ · 1 + 3 = 279.

Решим обратную задачу, найдя слово в данном трехбуквенном алфавите, имеющее номер 321.

Согласно приведенному выше алгоритму, получим

321 = 106 · 3 + 3 = (35 · 3 + 1)3 + 3 = (11 · 3 + 2)3² + 1 · 3 + 3 · 3⁰ = (3 · 3 + 2)3³ + 2 · 3² + 1 · 3 + 3 · 3⁰ = 3 · 3⁴ + 2 · 3³ + 2 · 3² + 1 · 3 + 3.

Следовательно, искомое слово есть сbbас. #

Лексикографическая нумерация напоминает способ упорядочения слов в словарях: однобуквенные слова следуют в порядке номеров букв в алфавите, среди двух двухбуквенных слов меньший номер имеет слово, начинающееся буквой с меньшим номером, и т.д. Но полного совпадения нет, так как в словаре слова группируются по начальной букве, а не по длине.

Нам будет удобно в дальнейшем использовать следующую запись непустого слова х в алфавите V по буквам:

х = х(1)х(2) ... x(k),

где x(i), 1 ≤ i ≤ k, - i-я буква слова х.

Определение 7.2. Языком в алфавите V называется произвольное подмножество множества V*.

Множество всех языков в алфавите V, т.е. множество 2^V*, есть булеан счетного множества, и, следовательно, оно в силу теоремы 1.15 Кантора имеет мощность континуума.

Наша следующая задача - определить на множестве 2^V* всех языков в произвольном (но фиксированном!) алфавите V алгебраическую структуру. На множестве 2^V* можно определять различные операции. Прежде всего языки - это множества, следовательно, над ними можно производить все те же операции, что и над множествами: объединение, пересечение, разность, дополненuе и т.п. Универсальное множество в данном случае есть множество слов V*, которое называют универсальным языком.

Кроме перечисленных теоретико-множественных операций можно рассматривать и специальные операции над языками. Прежде чем обратиться к этим операциям, определим операцию соединения (или конкатенации) слов. Соединением слов х = х(1)х(2) ... x(k) и у= у(1)у(2) ... у(m) называют слово ху = х(1)х(2) ... x(k)y(1)y(2) ... у(m).

По определению, считаем хλ = λх = х для любого х. Соединение иногда обозначают точкой ( · ).

Неформально соединение ху получается приписыванием слова у справа к слову х. Таким образом, для любых двух слов х ∈ V^k и у ∈ V^m конкатенация ху ∈ V^k+m (k,m ≥ 0). Следовательно, |xy| = |x| + |y|·

Из определения также следует, что соединение слов ассоциативно, т.е. для произвольных трех слов х, у, z имеет место x(yz) = (xy)z, и поэтому - с учетом написанного выше свойства пустого слова - множество V* всех слов в алфавите V с операцией соединения образует моноид (V*, ·, λ). Единица моноида - пустое слово. Этот моноид есть не что иное, как свободный моноид, порожденный алфавитом V (см. пример 2.7). Для него используют то же обозначение, что и для самого множества всех слов в алфавите V, т.е. V*.

На основе понятия соединения слов определим понятие вхождения одного слова в другое.

Определение 7.3. Вхождение слова х ∈ V* в слово у ∈ V* - это упорядоченная тройка слов (u, х, v), такая, что у = uхv.

При этом слово и называют левым, а слово v - правым крылом указанного вхождения. Слово х называют основой вzождения.

Говорят, что слово х входит в слово у, если существует вхождение х в у. При этом также слово (цепочку) х называют подсловом (или подцепочкой) слова (цепочки) у. Подцепочку х цепочки у называют началом (или префипсом) цепочки у, если у = xz для некоторой непустой цепочки z; если же для некоторой непустой цепочки z имеет место у = zx, то цепочку х называют концом (или постфиксом) цепочки у.

Заметим, что каждое слово входит в себя само и пустое слово входит в любое слово.

Например, слова "цикл" и "циклоп" входят в слово "энциклопедия". Соответствующие вхождения записывают следующим образом:

(эн, цикл, опедия), (эн, циклоп, едия).

Может существовать несколько разных вхождений одного и того же словах в некоторое слово у. Так, слово "абра" дважды входит в слово "абракадабра". Число вхождений пустого слова в данное слово р на единицу больше длины слова р. Среди всех вхождений слова х в слово у вхождение с наименьшей длиной левого крыла называют первым или главным вхождением х в у.

Так, вхождение (λ, абра, кадабра) есть первое вхождение слова "абра" в слово "абракадабра".

Определение 7.4. Говорят, что вхождения (u, х, v) и (s, z, t) слов х и z в одно и то же слово у не пересекаются, если существуют такие (может быть, и пустые) словари p и q, что у = uxpzt (и тогда v = pzt, а s = uxp) или у = szqxv (и тогда u = szq, а t = qxv) (рис. 7.1). В противном случае говорят, что указанные вхождения пересекаются.

Так, вхождения слов "цикл" и "циклоп" в слово "энциклопедия" пересекаются, а два разных вхождения слова "абра" в слово "абракадабра" не пересекаются. Мы иногда будем использовать обозначение х ⊑ у для утверждения "слово х входит в слово у". Можно доказать, что ⊑ - отношение порядка.

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

Определение 7.5. Соединением (конкатенацией) языков L₁ и L₂ называют язык L₁L₂, состоящий из всех возможных соединений слов ху, в которых слово х принадлежит первому, а слово у - второму языку, т.е.

L₁L₂ = {xy: x ∈ L₁ и y ∈ L₂}.

Соединение конечных языков легко вычислить.

Пример 7.2. Если V = {а, b, с}, L₁ = {аb, bсс, саb}, L₂ = = {са, bсс}, то

L₁L₂ = {аbса, аbbсс, bссса, bссbсс, саbса, саbbсс},

а

L₂L₁ = { сааb, саbсс, сасаb, bссаb, bссbсс, bсссаb}.

Вычисление конкатенации языков в конечном случае очень похоже на умножение (раскрытие скобок) в обычной школьной алгебре. Можно было бы формально написать так:

(аb + bсс + саb)(са + bсс) = аbса + аbbсс + bссса + bссbсс + саbса + саbbсс.

В данном случае плюс (+) - это только соединительный знак, используемый вместо запятой. Позже мы увидим, что подобным чисто формальным записям может быть придан строгий алгебраический смысл. #

Соединение языков не коммутативно, и, как показывает только что разобранный пример, пересечение L₁L₂ ∩ L₂L₁ в общем случае не пусто. В нашем примере оно содержит одну цепочку bссbсс.

Операция соединения языков позволяет определить операцию возведения языка в произвольную натуральную степень. А именно, по определению, L⁰ = {λ} для любого L ⊆ V*, а Lⁿ = L^n-1 при n > 0.

Итерацией языка L называют объединение всех его степеней:

Рассматривая объединение всех степеней языка L, начиная с первой, получим позитивную итерацию

Сформулируем основное алгебраическое свойство множества всех языков в алфавите V.

Теорема 7.1. Алгебра L(V) = (2^V*, ∪, ·, ∅, {λ}) есть замкнутое полукольцо.

◀ Проверка аксиом полукольца (см. 3) сводится к доказательству:

1. того, что по операции объединения множество всех языков образует коммутатuвный и идемпотентный моноид (с пустым множеством в качестве нейтрального элемента (нуль полукольца)); это тривиально ввиду известных свойств операции объединения множеств;
2. того, что по операции конкатенации множество языков образует моноид (с языком {λ}, состоящим из одного пустого слова, в качестве нейтрального элемента (единицы полукольца)); для этого достаточно доказать, что операция соединения языков ассоциативна, а также доказать для любого языка L тождество
   {λ}L = L{λ} = L,
   что вытекает из ассоциативности операции соединения слов и из тождества λх = хλ = х для любого словах;
3. следующих тождеств:
   L₁(L₂ ∪ L₃) =L₁L₂ ∪ L₁L₁,
   (L₁ ∪ L₂)L₃ = L₁L₃ ∪ L₂L₃
   (эти тождества определяют свойство дистрибутивности операции соединения относительно объединения).

Докажем первое из этих тождеств. Пусть слово х принадлежит его левой части, т.е языку L₁(L₂ ∪ L₃), Тогда, согласно определению соединения языков, это слово может быть представлено в виде х = yz, где у ∈ L₁, а z ∈ L₂ ∪ L₃, т.е. z ∈ L₂ или z ∈ L₃, Если z ∈ L₂, то yz ∈ L₁L₂, а если z ∈ L₃, то yz ∈ L₁L₃, т.е. х = yz ∈ L₁L₂ ∪ ∈ L₁L₃. Пусть теперь х ∈ L₁L₂ ∪ L₁L₃. Тогда х = yz, где у ∈ L₁, а z ∈ L₂ или z ∈ L₃, т.е. х ∈ L₁(L₂ ∪ L₃), что и завершает доказательство первого тождества. Второе доказывается аналогично.

Напомним, что в полукольце S = (S, +,·,0, 1) отношение порядка вводится следующим образом: для любых х, у ∈ S по определению полагают х ≤ у тогда и только тогда, когда х + у= у. Так как в полукольце всех языков в алфавите V операция сложения - это операция объединения множеств, то в данном случае отношение порядка есть не что иное, как теоретикомножественное включенuе ⊆ (действительно, включение L ⊆ К равносильно тому, что L ∪ К = К). Тогда замкнутость полукольца L(V) следует из существования объединения любого семейства множеств (в частности, бесконечной последовательности множеств - см. 1.5), служащего точной верхней гранью этого семейства (относительно теоретико-множественного включения), а также из следующих тождеств (для любого языка L и любого семейства языков P_i, i ∈ I):

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

Рассмотрим, например, доказательство второго тождества из (7.1), используя, как и выше, метод двух включенuй. Если

Согласно определению объединения семейства множеств, найдется такое i ∈ I, что у ∈ P_i и тогда yz = х ∈ P_iL, т.е.

Обратное включение доказываем так: из

следует, что для некоторого i ∈ I х ∈ P_iL, т.е. х = yz, где у ∈ P_i, а z ∈ L, откуда

Следствие 7.1. Для любого языка L верно тождество L⁺ =L*L=LL*.

◀ Вычислим соединение

Применяя первое из тождеств (7.1), получим

т.е. L⁺ = L*L. Тождество L⁺ = LL* доказывается аналогично. ▶

Заметим, что в общем случае нельзя утверждать, что позитивная итерация языка L получается выбрасыванием из обычной итерации пустого слова. Это верно в том и только в том случае, когда язык L не содержит пустого слова. Если же λ ∈ L, то L⁺ = L*, так как тогда L⁰ = {λ} ⊆ L.