Вопрос 2

Определение: алфавит - это конечное множество символов. (Термин "символ" имеет достаточно ясный интуитивный смысл и не нуждается в дальнейшем уточнении.)

Например, алфавит A = {a, b, c, +, !} содержит 5 букв, а алфавит B = {00, 01, 10, 11} содержит 4 буквы, каждая из которых состоит из двух символов.

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

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

Более формально цепочка символов в алфавите V определяется следующим образом:

(1)  - цепочка в алфавите V;

(2) если  - цепочка в алфавите V и a - символ этого алфавита, то a или а - цепочка в алфавите V;

  - цепочка в алфавите V тогда и только тогда, когда она является таковой в силу (1) и (2).

Определение: если  и  - цепочки, то цепочка  называется конкатенацией (или сцеплением) цепочек  и .

Например, если  = ab и  = cd, то  = abcd.

Для любой цепочки  всегда  =  = .

Определение: обращением (или реверсом) цепочки  называется цепочка, символы которой записаны в обратном порядке.

Обращение цепочки  будем обозначать ^R.

Например, если  = abcdef, то ^R = fedcba.

Для пустой цепочки:   ^R.

Определение: n-ой степенью цепочки будем обозначать ⁿ) называется конкатенация n цепочек 

⁰ = ; ⁿ = ^n-1 = ^n-1.

Определение: длина цепочки - это число составляющих ее символов.

Например, если  = abcdefg, то длина  равна 7.

Длину цепочки  будем обозначать ||. Длина  равна 0.

Определение: язык в алфавите V - это подмножество цепочек конечной длины в этом алфавите.

Определение: обозначим через V^* множество, содержащее все цепочки в алфавите V, включая пустую цепочку .

Например, если V={0,1}, то V^* = {, 0, 1, 00, 11, 01, 10, 000, 001, 011, ...}.

Определение: обозначим через V⁺ множество, содержащее все цепочки в алфавите V, исключая пустую цепочку .

Следовательно, V^* = V⁺  {.

Ясно, что каждый язык в алфавите V является подмножеством множества V^*.

Известно несколько различных способов описания языков [3]. Один из них использует порождающие грамматики. Именно этот способ описания языков чаще всего будет использоваться нами в дальнейшем.

Определение: декартовым произведением A  B множеств A и B называется множество {(a,b) | a  A, b  B}.

Цепочкой символов (или строкой) называют произвольную последовательность символов, записанных один за другим. Цепочка – это последовательность, в которую могут входить любые допустимые символы.

Понятие символа (или буквы) является базовым в теории формальных языков и не нуждается в определении.

Цепочки символов обозначают греческими буквами: α, β, γ, …

Цепочка – это необязательно некоторая осмысленная последовательность символов. Последовательность «аввв..аагрьь ,.лл» – пример цепочки символов.

Для цепочки символов важен состав и количество символов в ней, а также порядок символов в цепочке. Один и тот же символ может произвольное число раз входить в цепочку. Поэтому цепочки «а» и «аа», а также «аб» и «ба» – это разные цепочки символов. Цепочки символов α и β равны (совпадают), α = β, если они имеют один и тот же состав символов, одно и то же их количество и одинаковый порядок следования символов в цепочке.

Количество символов в цепочке называют длиной цепочки. Длина цепочки символов α обозначается как |α|. Очевидно, что если α = β, то и |α| = |β|.

Основной операцией над цепочками символов является операция конкатенации (объединения или сложения) цепочек.

Конкатенация (сложение, объединение) двух цепочек символов – это дописывание второй цепочки в конец первой. Конкатенация цепочек α и β обозначается как αβ. Выполнить конкатенацию цепочек просто: например, если α = «аб», а β = «вг», то αβ = «абвг».

Так как в цепочке важен порядок символов, то очевидно, что операция конкатенации не обладает свойством коммутативности, то есть в общем случае существуют α и β такие, что αβ ≠ βα. Также очевидно, что конкатенация обладает свойством ассоциативности, то есть (αβ)γ = α(βγ).

Можно выделить еще две операции над цепочками.

Обращение цепочки – это запись символов цепочки в обратном порядке. Обращение цепочки α обозначается как α^R. Если α = «абвг», то α^R = «гвба». Для операции обращения справедливо следующее равенство  ∀α,β: (αβ)^R = β^Rα^R. Т.е. обращение конкатенации равно конкатенации обращений.

Итерация (повторение) цепочки n раз, где n є N,

n > 0 – это конкатенация цепочки самой с собой n раз. Итерация цепочки α n раз обозначается как αⁿ. Для операции повторения справедливо следующее равенство∀ α: α¹ = α, α² = αα, α³ = ααα, … и т.д.

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

Для пустой цепочки справедливы следующие равенства:

1)   |λ| = 0 – Длина пустой цепочки;             Д

2)   ∀α: λα = αλ = α – Коммутативность;     К

3)   λ^R = λ – Обращение;                               О

4)   ∀ n ≥ 0: λⁿ = λ – Итерация;                     И

5)   ∀ α: α⁰ = λ.