Теория и реализация языков программирования
       

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


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

определить, принадлежит ли w языку L.

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

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

Пусть

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

Определим множество Tm как множество строк

длины не более n таких, что вывод
имеет не более m шагов. Ясно, что T0 = {S}.

Легко показать, что Tm можно получить из Tm-1

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

Если

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

Очевидно, что

для всех m > 1. Поскольку Tm зависит только от Tm-1, если Tm = Tm-1, то Tm = Tm+1 = Tm+2 = ... . Процедура будет вычислять T1, T2, T3, . . . пока для некоторого m не окажется Tm = Tm-1. Если w не принадлежит Tm, то не принадлежит и L(G), поскольку для j > m выполнено Tj = Tm. Если
то
.

Покажем, что существует такое m, что Tm = Tm-1. Поскольку для каждого i > 1 справедливо

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

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

. Обозначения имеют тот же смысл, что и для машин Тьюринга.

Содержание  Назад  Вперед






Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий