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


         

Первый трек будет содержать входную


Цепочку символов


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


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

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


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

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

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

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

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

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





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