Назад Оглавление Вперёд

2. Языки и их представление

2.1 Алфавиты, цепочки и языки

Алфавит, или словарь - это конечное множество символов. Для обозначения символов мы будем пользоваться цифрами, латинскими буквами и специальными литерами типа #, $.

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

Конкатенацией цепочек x и y называется цепочка xy. Заметим, что xe = ex = x для любой цепочки x.

Пусть x, y, z - произвольные цепочки в некотором алфавите. Цепочка y называется подцепочкой цепочки xyz. Цепочки x и y называются, соответственно, префиксом и суффиксом цепочки xy. Заметим, что любой префикс или суффикс цепочки является подцепочкой этой цепочки. Кроме того, пустая цепочка является префиксом, суффиксом и подцепочкой для любой цепочки.

Пример 2.1. Для цепочки abbba префиксом является любая цепочка из множества L₁ = {e, a, ab, abb, abbb, abbba}, суффиксом является любая цепочка из множества L₂ = {e, a, ba, bba, bbba, abbba}, подцепочкой является любая цепочка из множества L₁ L₂.

Длиной цепочки w (обозначается |w|) называется число символов в ней. Например, |abababa| = 7, а |e| = 0.

Язык в алфавите V - это некоторое множество цепочек в алфавите V .

Пример 2.2. Пусть дан алфавит V = {a, b}. Вот некоторые языки в алфавите V :

• L₁ = - пустой язык;
• L₂ = {e} - язык, содержащий только пустую цепочку

  (заметим, что L₁ и L₂ - различные языки);

• L₃ = {e, a, b, aa, ab, ba, bb} - язык, содержащий цепочки из a и b, длина которых не превосходит 2;
• L₄ - язык, включающий всевозможные цепочки из a и b, содержащие четное число a и четное число b;
• L₅ = {aⁿ² |n > 0} - язык цепочек из a, длины которых представляют собой квадраты натуральных чисел.

Два последних языка содержат бесконечное число цепочек.

Введем обозначение V ^* для множества всех цепочек в алфавите V , включая пустую цепочку. Каждый язык в алфавите V является подмножеством V ^*. Для обозначения множества всех цепочек в алфавите V , кроме пустой цепочки, будем использовать V ⁺.

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

Введем некоторые операции над языками.

Пусть L₁ и L₂ - языки в алфавите V . Конкатенацией языков L₁ и L₂ называется язык L₁L₂ = {xy|x L₁, y L₂}.

Пусть L - язык в алфавите V . Итерацией языка L называется язык L^*, определяемый следующим образом:

• L⁰ = {e};
• Lⁿ = LL^n-1, n 1;
• L^* = _n=0Lⁿ.

Пример 2.4. Пусть L₁ = {aa, bb} и L₂ = {e, a, bb}. Тогда

L₁L₂ = {aa, bb, aaa, bba, aabb, bbbb}, и

L₁^* = {e, aa, bb, aaaa, aabb, bbaa, bbbb, aaaaaa, ...}. Большинство языков, представляющих интерес, содержат бесконечное число цепочек. При этом возникают три важных вопроса.

Во-первых, как представить язык (т.е. специфицировать входящие в него цепочки)? Если язык содержит только конечное множество цепочек, ответ прост. Можно просто перечислить его цепочки. Если язык бесконечен, необходимо найти для него конечное представление. Это конечное представление, в свою очередь, будет строкой символов над некоторым алфавитом вместе с некоторой интерпретацией, связывающей это представление с языком.

Во-вторых, для любого ли языка существует конечное представление? Можно предположить, что ответ отрицателен. Мы увидим, что множество всех цепочек над алфавитом счетно. Язык - это любое подмножество цепочек. Из теории множеств известно, что множество всех подмножеств счетного множества несчетно. Хотя мы и не дали строгого определения того, что является конечным представлением, интуитивно ясно, что любое разумное определение конечного представления ведет только к счетному множеству конечных представлений, поскольку нужно иметь возможность записать такое конечное представление в виде строки символов конечной длины. Поэтому языков значительно больше, чем конечных представлений.

В-третьих, можно спросить, какова структура тех классов языков, для которых существует конечное представление?

2.2 Представление языков

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

Один из способов представления языка - дать алгоритм, определяющий, принадлежит ли цепочка языку. Более общий способ состоит в том, чтобы дать процедуру, которая останавливается с ответом «да» для цепочек, принадлежащих языку, и либо останавливается с ответом «нет», либо вообще не останавливается для цепочек, не принадлежащих языку. Говорят, что такая процедура или алгоритм распознает язык.

Такой метод представляет язык с точки зрения распознавания. Язык можно также представить методом порождения. А именно, можно дать процедуру, которая систематически порождает в определенном порядке цепочки языка.

Если мы можем распознать цепочки языка над алфавитом V либо с помощью процедуры, либо с помощью алгоритма, то мы можем и генерировать язык, поскольку мы можем систематически генерировать все цепочки из V ^*, проверять каждую цепочку на принадлежность языку и выдавать список только цепочек языка. Но если процедура не всегда заканчивается при проверке цепочки, мы не сдвинемся дальше первой цепочки, на которой процедура не заканчивается. Эту проблему можно обойти, организовав проверку таким образом, чтобы процедура никогда не продолжала проверять одну цепочку бесконечно. Для этого введем следующую конструкцию.

Предположим, что V имеет p символов. Мы можем рассматривать цепочки из V ^* как числа, представленные в базисе p, плюс пустая цепочка e. Можно занумеровать цепочки в порядке возрастания длины и в «числовом» порядке для цепочек одинаковой длины. Такая нумерация для цепочек языка {a, b, c}^* приведена на рис. 2.1, а.

Пусть P - процедура для проверки принадлежности цепочки языку L. Предположим, что P может быть представлена дискретными шагами, так что имеет смысл говорить об i-ом шаге процедуры для любой данной цепочки. Прежде чем дать процедуру перечисления цепочек языка L, дадим процедуру нумерации пар положительных чисел.

Все упорядоченные пары положительных чисел (x, y) можно отобразить на множество положительных чисел следующей формулой:

Пары целых положительных чисел можно упорядочить в соответствии со значением z (рис. 2.1, б).

Теперь можно дать процедуру перечисления цепочек L. Нумеруем упорядоченные пары целых положительных чисел - (1,1), (2,1), (1,2), (3,1), (2,2), ... . При нумерации пары (i, j) генерируем i-ю цепочку из V ^* и применяем к цепочке первые j шагов процедуры P. Как только мы определили, что сгенерированная цепочка принадлежит L, добавляем цепочку к списку элементов L. Если цепочка i принадлежит L, это будет определено P за j шагов для некоторого конечного j. При перечислении (i, j) будет сгенерирована цепочку с номером i. Легко видеть, что эта процедура перечисляет все цепочки L.

Если мы имеем процедуру генерации цепочек языка, то мы всегда можем построить процедуру распознавания предложений языка, но не всегда алгоритм. Для определения того, принадлежит ли x языку L, просто нумеруем предложения L и сравниваем x с каждым предложением. Если сгенерировано x, процедура останавливается, распознав, что x принадлежит L. Конечно, если x не принадлежит L, процедура никогда не закончится.

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

2.3 Грамматики

2.3.1 Формальное определение грамматики

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

Определение. Грамматика - это четверка G = (N, T, P, S), где

• N - алфавит нетерминальных символов;
• T - алфавит терминальных символов, N T = ;
• P - конечное множество правил вида , где (N T)^*N(N T)^*, (N T)^*;
• S N - начальный символ (или аксиома) грамматики.

Мы будем использовать большие латинские буквы для обозначения нетерминальных символов, малые латинские буквы из начала алфавита для обозначения терминальных символов, малые латинские буквы из конца алфавита для обозначения цепочек из T^* и, наконец, малые греческие буквы для обозначения цепочек из (N T)^*.

Будем использовать также сокращенную запись A ₁|₂|...|_n для обозначения группы правил A ₁, A ₂, ..., A _n.

Определим на множестве (N T)^* бинарное отношение выводимости следующим образом: если P, то для всех , (N T)^*. Если _{1 2}, то говорят, что цепочка ₂ непосредственно выводима из ₁.

Мы будем использовать также рефлексивно-транзитивное и транзитивное замыкания отношения , а также его степень k 0 (обозначаемые соответственно ^*, ⁺ и ^k). Если ₁ ^*₂ (₁ ⁺₂, ₁ ^k₂), то говорят, что цепочка ₂ выводима (нетривиально выводима, выводима за k шагов) из ₁.

Если ^k (k 0), то существует последовательность шагов

где = ₀ и = _k. Последовательность цепочек ₀, ₁, ₂, ..., _k в этом случае называют выводом из .

Сентенциальной формой грамматики G называется цепочка, выводимая из ее начального символа.

Языком, порождаемым грамматикой G (обозначается L(G)), называется множество всех ее терминальных сентенциальных форм, т.е.

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

Пример 2.5. Грамматика G = ({S, B, C}, {a, b, c}, P, S), где

P = {S aSBC, S aBC, CB BC, aB ab, bB bb, bC bc, cC cc}, порождает язык L(G) = {aⁿbⁿcⁿ|n > 0}.

Действительно, применяем n- 1 раз правило 1 и получаем a^n-1S(BC)^n-1, затем один раз правило 2 и получаем aⁿ(BC)ⁿ, затем n(n- 1)/2 раз правило 3 и получаем aⁿBⁿCⁿ.

Затем используем правило 4 и получаем aⁿbB^n-1Cⁿ. Затем применяем n- 1 раз правило 5 и получаем aⁿbⁿCⁿ. Затем применяем правило 6 и n - 1 раз правило 7 и получаем aⁿbⁿcⁿ. Можно показать, что язык L(G) состоит из цепочек только такого вида.

Пример 2.6. Рассмотрим грамматику G = ({S}, {0, 1}, {S 0S1, S 01}, S). Легко видеть, что цепочка 000111 L(G), так как существует вывод

Нетрудно показать, что грамматика порождает язык L(G) = {0ⁿ1ⁿ|n > 0}.

Пример 2.7. Рассмотрим грамматику G = ({S, A}, {0, 1}, {S 0S, S 0A, A 1A, A 1}, S). Нетрудно показать, что грамматика порождает язык L(G) = {0ⁿ1^m|n, m > 0}.

2.3.2 Типы грамматик и их свойства

Рассмотрим классификацию грамматик (предложенную Н.Хомским), основанную на виде их правил.

Определение. Пусть дана грамматика G = (N, T, P, S). Тогда

• если правила грамматики не удовлетворяют никаким ограничениям, то ее называют грамматикой типа 0, или грамматикой без ограничений.
• если
  • каждое правило грамматики, кроме S e, имеет вид , где ||||, и
  • в том случае, когда S e P, символ S не встречается в правых частях правил,

  то грамматику называют грамматикой типа 1, или неукорачивающей.

• если каждое правило грамматики имеет вид A , где A N, (N T)^*, то ее называют грамматикой типа 2, или контекстно-свободной (КС-грамматикой).
• если каждое правило грамматики имеет вид либо A xB, либо A x, где A, B N, x T^* то ее называют грамматикой типа 3, или праволинейной.

Легко видеть, что грамматика в примере 2.5 - неукорачивающая, в примере 2.6 - контекстно-свободная, в примере 2.7 - праволинейная.

Язык, порождаемый грамматикой типа i, называют языком типа i. Язык типа 0 называют также языком без ограничений, язык типа 1 - контекстно-зависимым (КЗ), язык типа 2 - контекстно-свободным (КС), язык типа 3 - праволинейным.

Теорема 2.1. Каждый контекстно-свободный язык может быть порожден неукорачивающей контекстно-свободной грамматикой.

Доказательство. Пусть L - контекстно-свободный язык. Тогда существует контекстно-свободная грамматика G = (N, T, P, S), порождающая L.

Построим новую грамматику G' = (N', T, P', S') следующим образом:

1. Если в P есть правило вида A ₀B₁₁...B_kk, где k 0, B_i ⁺e для 1 i k, и ни из одной цепочки _j (0 j k) не выводится e, то включить в P' все правила (кроме A e) вида

где X_i - это либо B_i, либо e.

2. Если S ⁺e, то включить в P' правила S' S, S' e и положить N' = N {S'}. В противном случае положить N' = N и S' = S.

Порождает ли грамматика пустую цепочку можноо установить следующим простым алгоритмом:

Шаг 1. Строим множество N_0 = N | N e

Шаг 2. Строим множество N_i = N | N N_i - 1^*

Шаг 3. Если N_i = N_i-1, перейти к шагу 4, иначе шаг 2.

Шаг 4. Если S N_i, значитS e.

Легко видеть, что G' - неукорачивающая грамматика. Можно показать по индукции, что L(G') = L(G). __

Пусть K_i - класс всех языков типа i. Доказано, что справедливо следующее (строгое) включение: K₃ K₂ K₁ K₀.

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

Пример 2.8. Рассмотрим грамматику G = ({S, A, B}, {0, 1}, {S AB, A 0A, A 0, B 1B, B 1}, S). Эта грамматика является контекстно-свободной. Легко показать, что L(G) = {0ⁿ1^m|n, m > 0}. Однако, в примере 2.7 приведена праволинейная грамматика, порождающая тот же язык.

Покажем что существует алгоритм, позволяющий для произвольного КЗ-языка L в алфавите T, и произвольной цепочки w T^* определить, принадлежит ли w языку L.

Теорема 2.2. Каждый контекстно-зависимый язык является рекурсивным языком.

Доказательство. Пусть L - контекстно-зависимый язык. Тогда существует некоторая неукорачивающая грамматика G = (N, T, P, S), порождающая L.

Пусть w T^* и |w| = n. Если n = 0, т.е. w = e, то принадлежность w L проверяется тривиальным образом. Так что будем предполагать, что n > 0.

Определим множество T_m как множество строк u (N T)⁺ длины не более n таких, что вывод S ^*u имеет не более m шагов. Ясно, что T₀ = {S}.

Легко показать, что T_m можно получить из T_m-1 просматривая, какие строки с длиной, меньшей или равной n можно вывести из строк из T_m-1 применением одного правила, т.е.

Если S ^*u и |u| n, то u T_m для некоторого m. Если из S не выводится u или |u| > n, то u не принадлежит T_m ни для какого m.

Очевидно, что T_m T_m-1 для всех m 1. Поскольку T_m зависит только от T_m-1, если T_m = T_m-1, то T_m = T_m+1 = T_m+2 = ... . Процедура будет вычислять T₁, T₂, T₃, . . . пока для некоторого m не окажется T_m = T_m-1. Если w не принадлежит T_m, то не принадлежит и L(G), поскольку для j > m выполнено T_j = T_m. Если w T_m, то S ^*w.

Покажем, что существует такое m, что T_m = T_m-1. Поскольку для каждого i 1 справедливо T_i T_i-1, то если T_iT_i-1, то число элементов в T_i по крайней мере на 1 больше, чем в T_i-1. Пусть |N T| = k. Тогда число строк в (N T)⁺ длины меньшей или равной n равно k + k² + ... + kⁿ nkⁿ. Только эти строки могут быть в любом T_i. Значит, T_m = T_m-1 для некоторого m nkⁿ. Таким образом, процедура, вычисляющая T_i для всех i 1 до тех пор, пока не будут найдены два равных множества, гарантированно заканчивается, значит, это алгоритм. __

Назад Оглавление Вперёд