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




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


Цепочку символов
s^1_1 \ldots s^1_n

n будем называть " первым треком ",

s^2_1 \ldots s^2_n

n - " вторым треком ". Первый трек будет содержать входную строку x с концевыми маркерами. Второй трек будет использоваться для вычислений. На первом шаге M помещает символ S в самой левой ячейке второго трека. Затем M выполняет процедуру генерации в соответствии со следующими шагами:

  1. Процедура выбирает подстроку символов
    из второго трека такую, что
    \alpha \rightarrow \beta \in P
    .
  2. Подстрока
    заменяется на ?, перемещая, если необходимо, вправо символы справа от
    . Если эта операция могла бы привести к перемещению символа за правый концевой маркер, ЛОА останавливается.
  3. Процедура недетерминированно выбирает перейти на шаг 1 или завершиться.

На выходе из процедуры первый трек все еще содержит строку x, а второй трек содержит строку ? такую, что

S \Rightarrow_G^*G \; \gamma
ЛОА сравнивает символы первого трека с соответствующими символами второго трека. Если сравнение неуспешно, строки символов первого и второго треков не одинаковы и ЛОА останавливается без допуска. Если строки одинаковы, ЛОА останавливается и допускает.

Если

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

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

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

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


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