Линейно-ограниченные автоматы и их связь с контекстно-зависимыми грамматиками

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

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

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

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

Определим множество Tm как множество строк длины не более n таких, что вывод имеет не более m шагов. Ясно, что T₀ = {S}.

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

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

Очевидно, что для всех m > 1. Поскольку T_m зависит только от T_m-1, если Tm = 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. Если , то .

Покажем, что существует такое m, что T_m = T m-1. Поскольку для каждого i > 1 справедливо , то если , то число элементов в T_i по крайней мере на 1 больше, чем в T_i-1. Пусть . Тогда число строк в длины меньшей или равной n равно . Только эти строки могут быть в любом T_i. Значит, T_m = T_m-1 для некоторого . Таким образом, процедура, вычисляющая T_i для всех до тех пор, пока не будут найдены два равных множества, гарантированно заканчивается, значит, это алгоритм.

Линейно-ограниченный автомат (ЛОА) - это недетерминированная машина Тьюринга с одной лентой, которая никогда не выходит за пределы |w| ячеек, где w - вход. Формально, линейно-ограниченный автомат обозначается как . Обозначения имеют тот же смысл, что и для машин Тьюринга. Q - это множество состояний, - множество заключительных состояний, - множество ленточных символов, - множество входных символов, - начальное состояние, D - отображение из в подмножество .

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

Конфигурация M и отношение , связывающее две конфигурации, если вторая может быть получена из первой применениемD, определяются так же, как и для машин Тьюринга. Конфигурация M обозначается как

(q,A₁A₂,...,A_n,i) где -целое от 1 до n. Предположим, что и i > 1

Будем говорить, что

и i < n, будем говорить, что

То есть M печатает A поверх A_i, меняет состояние на p и передвигает головку влево или вправо, но не за пределы области, в которой символы располагались исходно. Как обычно, определим отношение как

и

Если и ,

то

Язык, допускаемый M - это и для некоторого и целого i}.

Будем называть M детерминированным, если D(q, A) содержит не более одного элемента для любых . Не известно, совпадает ли класс множеств, допускаемых детерминированными и недетеминированными ЛОА. Ясно, что любое множество, допускаемое недетерминированным ЛОА, допускается некоторой детерминированной МТ. Однако, число ячеек ленты, требуемой этой МТ, может экспоненциально зависеть от длины входа.

Класс множеств, допускаемых ЛОА, в точности совпадает с классом контекстно - зависимых языков.

Теорема 2.7. Если L - контекстно-зависимый язык, то L допускается ЛОА.

Доказательство. Пусть G = (V_N, V_T, P, S) - контекстно- зависимая грамматика. Построим ЛОА M такой, что он допускает языкL(G). Не вдаваясь в детали построения M, поскольку он довольно сложен, рассмотрим схему его работы. В качестве ленточных символов будем рассматривать пары В начальной конфигурации лента содержит (@, B), (a₁, B), ... (a_n, B), ($, B), где a¹ ... a_n = w - входная цепочка,n=|w|. Цепочку символов n будем называть " первым треком ", n - " вторым треком ". Первый трек будет содержать входную строку x с концевыми маркерами. Второй трек будет использоваться для вычислений. На первом шагеM помещает символ S в самой левой ячейке второго трека. Затем M выполняет процедуру генерации в соответствии со следующими шагами:

1. Процедура выбирает подстроку символов из второго трека такую, что .

2. Подстрока заменяется на перемещая, если необходимо, вправо символы справа от . Если эта операция могла бы привести к перемещению символа за правый концевой маркер, ЛОА останавливается.

3. Процедура недетерминированно выбирает перейти на шаг 1 или завершиться.

На выходе из процедуры первый трек все еще содержит строку x, а второй трек содержит строку такую, что ЛОА сравнивает символы первого трека с соответствующими символами второго трека. Если сравнение неуспешно, строки символов первого и второго треков не одинаковы и ЛОА останавливается без допуска. Если строки одинаковы, ЛОА останавливается и допускает.

Если , то существует некоторая последовательность шагов, на которой ЛОА строит x на втором треке и допускает вход. Аналогично, для того, чтобы ЛОА допустил x, должна существовать последовательность шагов такая, что xможет быть построен на втором треке. Таким образом, должен быть вывод x из S в G.

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

Теорема 2.8. Если L допускается ЛОА, то L - контекстно - зависимый язык.

Доказательство. Конструкция КЗГ по ЛОА аналогична конструкции грамматики типа 0, моделирующей машину Тьюринга. Различие заключатся в том, что нетерминалы КЗГ должны указывать не только текущее и исходное содержимое ячеек ленты ЛОА, но и то, является ли ячейка соседней справа или слева с концевым маркером. Кроме того, состояние ЛОА должно комбинироваться с символом под головкой, поскольку КЗГ не может иметь раздельные символы для концевых маркеров и состояния ЛОА, так как эти символы должны были бы быть заменены на e, когда строка превращается в терминальную.

Теорема 2.9. Существуют рекурсивные множества, не являющиеся контекстно - зависимыми.

Доказательство. Все строки в {0,1}^* можно занумеровать. Пусть x_i - i -ое слово. Мы можем занумеровать все грамматики типа0, терминальными символами которых являются 0 и 1. Поскольку имена переменных не важны и каждая грамматика имеет конечное их число, можно предположить, что существует счетное число переменных.

Представим переменные в двоичной кодировке как 01, 011, 0111, 01111 и т.д. Предположим, что 01 всегда является стартовым символом. Кроме того, в этой кодировке терминал 0 будет представляться как 00, а терминал 1 как 001. Символ" -> " представляется как 0011, а запятая как 00111. Любая грамматика с терминалами 0 и 1 может быть представлена строкой правил, использующей стрелку (0011) для разделения левой и правой частей, и запятой (00111) для разделения правил. Строки, представляющие символы, используемые в правилах, - это 00, 001 и 01ⁱ для i = 1, 2, ... Множество используемых переменных определяется неявно правилами.

Отметим, что не все строки из 0 и 1 представляют грамматики, и не обязательно КЗГ. Однако, по данной строке легко можно сказать, представляет ли она КЗГ. i - ю грамматику можно найти, генерируя двоичные строки в описанном порядке пока не сгенерируется i -я строка, являющаяся КЗГ. Поскольку имеется бесконечное число КЗГ, их можно занумеровать в некотором порядке G₁, G₂, ...

Определим . L рекурсивно. По строке x_i легко можно определить i и затем определить G_i.По теореме 2.6. имеется алгоритм, определяющий для x_i принадлежит ли он L(G_i), поскольку G_i КЗГ. Таким образом имеетсяалгоритм для определения для любого x принадлежит ли он G.

Покажем теперь, что L не генерируется никакой КЗ-грамматикой. Предположим, что L генерируется КЗ- грамматикой G_i. Во-первых, предположим, что . Поскольку . Но тогда по определению - противоречие. Таким образом предположим, что . Поскольку . Но тогда по определению - снова противоречие. Из чего можно заключить, что L не генерируется G_i. Поскольку приведенный выше аргумент справедлив для каждой КЗ- грамматики G_i в перечислении, и поскольку перечислениесодержит все КЗ-грамматики, можно заключить, что L не КЗ-язык. Поэтому L - рекурсивное множество, не являющееся контекстно-зависимым.