Изменения
→Связь линейно ограниченных автоматов с контекстно-зависимыми языками
Если <tex>L</tex> — [[Иерархия Хомского формальных грамматик#Класс 1|контекстно-зависимый язык]], то язык <tex>L</tex> принимается некоторым линейно ограниченным автоматом.
|proof=
Пусть <tex>G = \langle V_N \Sigma , V_TN, S, P, S\rangle</tex> — контекстно-зависимая грамматика. Мы построим линейный ограниченный автомат <tex>M</tex>, такой, что язык, принимаемый <tex>M</tex>, есть <tex>L(G)</tex>.
Входная лента будет иметь две дорожки. Первая дорожка будет содержать входную строку <tex>x (x \ne \varepsilon)</tex> с концевыми маркерами. Вторая дорожка будет использоваться для работы.
#Подпрограмма выбирает последовательные подстроки символов <tex>\alpha</tex> на второй дорожке, такие, что <tex>\alpha \rightarrow \beta \in P</tex>.
#Подстроки <tex>\alpha</tex> заменяются на <tex>\beta</tex>, сдвигая вправо, если необходимо, символы, расположенные справа от <tex>\alpha</tex>. Если эта операция заставляет символ быть вытолкнутым за правый маркер, автомат останавливается. Как известно, промежуточные сентенциальные формы в контекстно-зависимой грамматике не длиннее, чем выводимая терминальная цепочка. Так что, если на очередном шаге получена строка длиннее <tex>x</tex>, то продолжать процесс не имеет смысла, потому что все последующие строки будут разве лишь длиннее.
#Подпрограмма недетерминированно выбирает, возвращаться ли к шагу 1, либо идти на выход.
#При выходе из подпрограммы первая дорожка все еще будет содержать строку <tex>x</tex>, в то время как вторая дорожка будет содержать некоторую строку <tex>y</tex>, такую, что <tex>S \Rightarrow^*_M y</tex>.
