Изменения
Нет описания правки
Из определения следует, что языком, принимаемым линейно ограниченным автоматом <tex>M</tex>, называется множество
<tex>L(M) = \{w|\mid w\in(\Sigma\setminus\{\#,\$\})^*,</tex> <tex> (q0,\#w\$,1)\vdash^*_M(q,\#\alpha\$,i),q\in F,\alpha \in \Gamma^*</tex><tex>, 1 \le leqslant i\le leqslant n,n = |w|+2\}.</tex>
Пусть <tex>G = \langle V_N , V_T, P, S\rangle</tex> — контекстно-зависимая грамматика. Мы построим линейный ограниченный автомат <tex>M</tex>, такой, что язык, принимаемый <tex>M</tex>, есть <tex>L(G)</tex>.
Входная лента будет иметь две дорожки. Первая дорожка будет содержать входную строку <tex>x (x \ne \epsilonvarepsilon)</tex> с концевыми маркерами. Вторая дорожка будет использоваться для работы.
На первом шаге <tex>M</tex> помещает символ <tex>S</tex> в крайнюю левую ячейку второй дорожки. Затем автомат входит в порождающую подпрограмму, которая выполняет следующие шаги:
Для доказательства этой теоремы построим контекстно-зависимую грамматику, которая моделирует линейно ограниченный автомат.
Нетерминалы контекстно-зависимой грамматики должны указывать не только первоначальное содержание некоторой ячейки ленты линейно ограниченного автомата, но также и то, является ли эта ячейка смежной с концевым маркером слева или справа. Такие ячейки в обозначении нетерминалов мы будем снабжать маркерами <tex>\#</tex> и <tex>\$</tex>, обозначающими, что ячейка граничит соответственно с левым, правым или обоими концевыми маркерами. В обозначении нетерминала состояние линейно ограниченного автомата должно также комбинироваться с символом, находящимся под головкой ленты. Контекстно-зависимая грамматика не может иметь отдельных символов для концевых маркеров и состояния линейно ограниченного автомата, потому что эти символы должны были бы заменяться на пустые цепочки, когда строка превращается в терминальную, а <tex>\epsilonvarepsilon</tex>-порождения в контекстно-зависимой грамматике запрещены.
В грамматике необходимо поддерживать три типа операций:
