Составители:
119
линейно ограниченным автоматом, принимается некоторой детерминирован-
ной машиной Тьюринга. Однако длина ленты
: , требуемая этой Tm, может быть
экспоненциальной, а не линейной, функцией от длины входной цепочки.
§ 8.2. Связь линейно ограниченных автоматов
с контекстно-зависимыми языками
Наш интерес к недетерминированным линейно ограниченным автоматам
проистекает из того факта, что класс множеств, принимаемых ими, является в
точности классом контекстно-зависимых языков.
Теорема 8.1. Если L — контекстно-зависимый язык, то язык L принимается
некоторым линейно ограниченным автоматом.
Доказательство. Пусть G =(V
N
, V
T
, P, S) — контекстно-зависимая грам-
матика. Мы построим lba M, такой, что язык, принимаемый lba M, есть L(G).
Мы не будем вдаваться в детальное построение автомата M, поскольку оно
очень сложно, а просто опишем, как он работает.
Входная лента будет иметь две дорожки. Дорожка 1 будет содержать
входную строку x (x ≠ε) с концевыми маркерами. Дорожка 2 будет
использоваться для работы.
На
первом шаге lba M помещает символ S в крайнюю левую ячейку дорожки 2.
Затем автомат входит в порождающую подпрограмму, которая выполняет
следующие шаги:
1. Подпрограмма выбирает последовательные подстроки символов α на
дорожке 2, такие, что α→β∈P.
2. Подстроки α заменяются на β, сдвигая вправо, если необходимо, символы,
расположенные справа от α. Если эта операция заставляет символ быть вытол-
кнутым за правый маркер, lba M останавливается
11
при этом выборе движений.
3. Подпрограмма недетерминированно выбирает, возвращаться ли к шагу 1,
либо идти на выход.
При
выходе из подпрограммы дорожка 1 все ещё будет содержать строку x, в
то время как дорожка 2 будет содержать некоторую строку γ, такую, что S
γ.
Lba M сравнивает посимвольно цепочки x и γ. Если окажется, что x ≠γ, то lba M
останавливается, не принимая. Если же окажется, что x = γ, то он останав-
ливается, принимая входную цепочку.
Если x∈ L(G), то существует некоторая последовательность движений, при
которой lba M строит цепочку x на дорожке 2, которая принимается.
Аналогично, чтобы lba M принял цепочку x, должна существовать последова-
тельность движений, генерирующих цепочку x на дорожке 2. Таким образом,
должен быть вывод S
x.
Теорема доказана.
11
Как известно, промежуточные сентенциальные формы в контекстно-зависимой грам-
матике не длиннее, чем выводимая терминальная цепочка. Так что, если на очередном шаге
получена сентенциальная форма длиннее
x, то продолжать процесс не имеет смысла, потому
что все последующие сентенциальные формы будут разве лишь длиннее.
*
G
⇒
*
G
⇒
Страницы
- « первая
- ‹ предыдущая
- …
- 118
- 119
- 120
- 121
- 122
- …
- следующая ›
- последняя »
