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




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


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

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

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

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

Пусть

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

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

u \in (N \cup T)^+
длины не более n таких, что вывод
S \Rightarrow^* \; u
имеет не более m шагов. Ясно, что T0 = {S}.

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

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

T_m=T_{m-1} \cup \{u \mid v \Rightarrow для \; некоторого \; v \in T_{m-1}, \;где \mid \! u \! \mid \leq n \}

Если

S\Rightarrow^* \; u
и
\mid \!u \! \mid \leq n, \; то \; u \in T_m
для некоторого m. Если из S не выводится u или |u| > n, то u не принадлежит Tm ни для какого m.

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

T_m \subseteq T_{m-1}
для всех 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. Если
w \in T_m,
то
S \Rightarrow^* w
.

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

T_i \supseteq T_{i-1}
, то если
T_i \neq T_{i-1}
, то число элементов в Ti по крайней мере на 1 больше, чем в Ti-1. Пусть
\mid \! N \cup T \! \mid = k
. Тогда число строк в
( N \cup T )^+
длины меньшей или равной n равно
k+k^2+ \ldots +k^n \leq nk^n
. Только эти строки могут быть в любом Ti. Значит, Tm = Tm-1 для некоторого
m \leq nk^n
. Таким образом, процедура, вычисляющая Ti для всех
i \geq 1
до тех пор, пока не будут найдены два равных множества, гарантированно заканчивается, значит, это алгоритм.

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

M = (Q, \Sigma, \Gamma, D, q_0, F)
. Обозначения имеют тот же смысл, что и для машин Тьюринга.


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