Пусть дан алфавит V = {a, b}. Вот некоторые языки в алфавите V:
1) L1 = Æ – пустой язык;
2) L2 = {e} – язык, содержащий только пустую цепочку
(заметим, что L1 и L2 – различные языки);
3) L3 = {e, a, b, aa, ab, ba, bb} – язык, содержащий цепочки из a и b, длина которых не превосходит 2;
4) L4 = {an2 | n > 0} – язык цепочек из a, длины которых представляют собой квадраты натуральных чисел. Данный язык содержит бесконечное число цепочек.
Обозначим через V* множество, содержащее все цепочки в алфавите V, включая пустую цепочку e.
Обозначим через V+ множество, содержащее все цепочки в алфавите V, исключая пустую цепочку e.
Следовательно, V* = V+ È {e}.
Ясно, что каждый язык в алфавите V является подмножеством множества V*.
Большинство языков, представляющих интерес, содержат бесконечное число цепочек. При этом возникает важный вопрос: как представить язык, то есть специфицировать входящие в него цепочки? Если язык содержит только конечное множество цепочек, то можно просто перечислить его цепочки. Если язык бесконечен, необходимо найти для него конечное представление. Это конечное представление, в свою очередь, будет строкой символов над некоторым алфавитом вместе с некоторой интерпретацией, связывающей это представление с языком.
Известно несколько различных способов описания языков [3]:
1. Язык представляется перечислением правильных предложений языка, заданных над некоторым алфавитом.
Пусть задан некий алфавит V, тогда язык над этим алфавитом L(V) - это множество таких цепочек a, которые принадлежат V*:
L(V) = {a|aÎV* }
2. Использование порождающей грамматики, которая содержит правила получения правильных предложений языка.
Второй способ описания языков чаще всего будет использоваться нами в дальнейшем.
3. Распознавательная модель языка: определяется некоторое абстрактное устройство, которое для любого предложения, поданного на вход этого устройства, отвечает, является ли это предложение правильным в данном языке или неправильным (рис. 2.1).
Процедура – это конечная последовательность инструкций, которые могут быть механически выполнены. Примером может служить машинная программа. Процедура, которая всегда заканчивается, называется алгоритмом.
Один из способов представления языка – дать алгоритм, определяющий, принадлежит ли цепочка языку. Более общий способ состоит в том, чтобы дать процедуру, которая останавливается с ответом “да” для цепочек, принадлежащих языку, и либо останавливается с ответом “нет”, либо вообще не останавливается для цепочек, не принадлежащих языку. Говорят, что такая процедура или алгоритм распознает язык. Данный метод представляет язык с точки зрения распознавания.
Язык можно также представить методом порождения. А именно, можно дать процедуру, которая систематически порождает в определенном порядке цепочки языка. Действительно, если можно распознавать цепочки языка над алфавитом V либо с помощью процедуры, либо с помощью алгоритма, то можно и генерировать язык: последовательно генерировать все цепочки из V*, проверять каждую цепочку на принадлежность языку и выдавать список только цепочек языка. Однако в том случае, когда процедура не всегда заканчивается при проверке цепочки, может произойти зацикливание, то есть процедура может проверять одну цепочку бесконечно. Эту проблему можно обойти, организовав проверку цепочки на принадлежность языку следующим образом.
Предположим, что V имеет p символов. Мы можем рассматривать цепочки из V * как числа, представленные в базисе p, плюс пустая цепочка e. Можно занумеровать цепочки в порядке возрастания длины и в “числовом” порядке для цепочек одинаковой длины. Такая нумерация для цепочек языка {a, b, c}* приведена на рис. 2.2, а.
Пусть P – процедура для проверки принадлежности цепочки языку L. Предположим, что P может быть представлена дискретными шагами, так что имеет смысл говорить об i-ом шаге процедуры для любой данной цепочки. Прежде чем дать процедуру перечисления цепочек языка L, дадим процедуру нумерации пар положительных чисел.
Все упорядоченные пары положительных чисел (x, y) можно отобразить на множество положительных чисел следующей формулой:
z = (x + y - 1)(x + y - 2)/2+ y
Пары целых положительных чисел можно упорядочить в соответствии со значением z (рис. 2.2, б).
y
1 e
2 a
3 b
4 c
5 aa
Z (x, y)
x
6 ab
7 ac
8 ba
9 bb
... ...
а) б)
Рис. 2.2.
Теперь можно дать процедуру перечисления цепочек 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 a
4 c