Основные термины

Опр. Алфавит V - конечное непустое множество элементов, называемых символами (буквами).

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

Пример. Рассмотрим алфавит V = {a,b,c}. Тогда baaa является словом в алфавите V.

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

Опр. Длиной цепочки w называется число составляющих ее символов (обозначается |w|), причём каждый символ считается столько раз, сколько раз он встречается в w.

Пример. Очевидно, |baaa| = 4 и || = 0.

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

Пример. Пусть V = {1,0}, тогда V* = {,0,l, 00,01,10,11,000,...}, а V⁺ = {0,1,00,01,10,11,000,...}.

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

Опр. Если х - слово и п  N, то через х^п обозначается слово х  х  ...  x. По определению х⁰ = .

Пример. ba³ = bааа и (ba)³ = bababa.

Опр. Говорят, что слово х - префикс (начало) слова у, если у = хи.

Опр. Говорят, что слово х - суффикс (конец) слова у, если у = их.

Опр. Говорят, что слово х — подслово слова у, если у = uxv для некоторых слов и и v.

Опр. Через |w|_a обозначается количество вхождений символа а в слово w.

Пример. Если V = {a,b,c}, то |baaa|_а = 3, |baaa|_b = 1 и |baaa|_c = 0.

Опр. Формальный язык – это множество конечных слов (строк, цепочек) над конечным алфавитом V.

Поскольку каждый язык является множеством, можно рассматривать операции объединения, пересечения, разности и дополнения языков, заданных над одним и тем же алфавитом (обозначения L₁  L₂, L₁  L₂, L₁ — L₂).

Пример. Множество {a, abb} является языком над алфавитом {a,b}.

Пример. Множество {a^kba^l | k ≤ l} является языком над алфавитом {a,b}.

Необходимо различать пустой язык L=0 и язык, содержащий только пустую цепочку: L={}≠0.

Опр. Пусть L – язык над алфавитом V*. Тогда язык V* — L называется дополнением языка L относительно алфавита V. Когда из контекста ясно, о каком алфавите идёт речь, говорят просто, что язык V* — L является дополнением языка L.

Опр. Грамматика – система правил, предназначенная для задания множества цепочек и символов данного алфавита.

G – грамматика; L(G) – язык этой грамматики.

Характеристика языка: семантика, синтаксис.

Можно выделить 3 группы формальных грамматик:

1. Порождающие (позволяют строить правильную цепочку в заданном алфавите с описанием ее строения и не позволяют строить ни одной неправильной цепочки)

2. Распознающие (позволяют определить к каждой входной цепочке: является ли она правильной; в случае положительного ответа распознающая ф.г. выдает строение цепочки)

3. Преобразующие (для каждой правильно построенной цепочки способны построить ее отображение в виде другой цепочки и вывести информацию о порядке проведения изображения)

Известны различные способы описания языков. Конечный язык можно описать простым перечислением его цепочек. Поскольку формальный язык может быть и бесконечным, требуются механизмы, позволяющие конечным образом представлять бесконечные языки. Можно выделить два основных подхода для такого представления: механизм распознавания и механизм порождения (генерации).

Механизм распознавания (распознаватель), по сути, является процедурой специального вида, которая по заданной цепочке определяет, принадлежит ли она языку. Если принадлежит, то процедура останавливается с ответом «да», т. е. допускает цепочку; иначе – останавливается с ответом «нет» или зацикливается. Язык, определяемый распознавателем - это множество всех цепочек, которые он допускает.

Примеры распознавателей:

• Машина Тьюринга (МТ). Язык, который можно задать с помощью МТ, называется рекурсивно перечислимым. Вместо МТ можно использовать эквивалентные алгоритмические схемы: нормальный алгоритм Маркова (НАМ), машину Поста и др.

• Линейно ограниченный автомат (ЛОА). Представляет собой МТ, в которой лента не бесконечна, а ограничена длиной входного слова. Определяет контекстно-зависимые языки.

• Автомат с магазинной (внешней) памятью (МП-автомат). В отличие от ЛОА, головка не может изменять входное слово и не может сдвигаться влево; имеется дополнительная бесконечная память (магазин, или стек), работающая по дисциплине LIFO. Определяет контекстно-свободные языки.

• Конечный автомат (КА). Отличается от МП-автомата отсутствием магазина. Определяет регулярные языки.

Основной способ реализации механизма порождения — использование порождающих грамматик, которые иногда называют грамматиками Хомского. Порождающие ф.г. являются наиболее важной и распространенной ф.г. На b[ изучении мы и остановимся подробно.

Порождающей ф.г. называется четверка вида: G = (V_T,V_N,P,S),

где Vn - конечное множество нетерминальных символов грамматики (обычно прописные латинские буквы);

Vt - множество терминальных символов грамматики (обычно строчные латинские буквы, цифры, и т.п.), V_TV_N =0,

Р - множество правил вывода грамматики; элемент (α,β) множества Р называется правилом вывода и записывается в виде α→β (читается: «из цепочки α выводится цепочка β»)

S - начальный символ грамматики, S  V_N.

Для записи правил вывода с одинаковыми левыми частями вида α→β1, α→β2,…,α→βn используется сокращенная форма записи α→β1|β2|…|βn.

Пример. Грамматика G1=({0, 1}, {A, S}, Р₁, S), где множество Р₁ состоит из правил вида: 1) S→0A1; 2) 0А→00А1; 3)А→.

Опр. Цепочка β (V_T  V_N)* непосредственно выводима из цепочки α(V_TV_N)⁺в грамматике G = (V_T,V_N,P,S) (обозначается: αβ), если α=ξ₁γξ₂ и β=ξ₁δξ₂ , где ξ₁,ξ₂,δ  V*, γV⁺ и правило вывода γ→δ содержится во множестве Р.

Опр. Цепочка βV* выводима из цепочки αV⁺ в грамматике G = (V_T,V_N,P,S) (обозначается: α*β), если существует последовательность цепочек γ0,γ1,…,γn (n≥0) такая, что α=γ0γ1…γn=β.

Пример. В грамматике G₁ S=>*000111, т.к. существует вывод S => 0А1 => 00А11 => 000A111 => 000111.

Опр. Языком, порожденным грамматикой G = (V_T, V_N,P, S), называется множество всех цепочек в алфавите Vt, которые выводимы из начального символа грамматики S с помощью правил множества Р, т.е. множество L(G) = {αV* |S*α}.

Пример. Для грамматики G₁ L(G1)={0ⁿ1ⁿ | п>0}.

Опр. Цепочка αV*, для которой существует вывод S*α, называется сентенциальной формой в грамматике G = (V_T, V_N,P, S).

Опр. Грамматики G₁ и G₂ называются эквивалентными, если L(G₁) = L(G₂).

Пример. Для грамматики G₁ эквивалентной будет грамматика G2 = ({0, 1}, {S}, Р₂, S), где множество правил вывода Р₂ содержит правила вида S→0S1|01.