1632
правки
Изменения
м
* Мартыненко Б.К. Языки и трансляции: Учеб. пособие ISBN 5-288-02870-2* [http://drona.csa.iisc.ernet.in/~deepakd/atc-2011/lba.pdf|Linear Bounded Automata by Indu John] [[Категория: Теория формальных языков]][[Категория: Теория вычислимости]][[Категория: Вычислительные формализмы]]
rollbackEdits.php mass rollback
Из определения следует, что языком, принимаемым линейно ограниченным автоматом <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 \leqslant i \leqslant n, \ n = |w| + 2\}.</tex>
Если <tex>L</tex> — [[Иерархия Хомского формальных грамматик#Класс 1|контекстно-зависимый язык]], то язык <tex>L</tex> принимается некоторым линейно ограниченным автоматом.
|proof=
Пусть <tex>G \Gamma = \langle V_N \Sigma , N, V_TS, P, S\rangle</tex> — контекстно-зависимая грамматика. Мы построим линейный ограниченный автомат <tex>M</tex>, такой, что язык, принимаемый <tex>M</tex>, есть <tex>L(G\Gamma)</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>.
Автомат <tex>M</tex> сравнивает посимвольно цепочки <tex>x</tex> и <tex>y</tex>. Если окажется, что <tex>x \ne y</tex>, то автомат останавливается, не принимая, если же окажется, что <tex>x = y</tex>, то он останавливается, принимая входную цепочку. Ясно, что если <tex>x \in L(G\Gamma )</tex>, то найдется такая последовательность движений <tex>M</tex>, которая сгенерирует цепочку <tex>x</tex> на второй дорожке, и тогда автомат остановится, принимая. Аналогично, если <tex>M</tex> принимает цепочку <tex>x</tex>, то должна существовать последовательность движений, генерирующих цепочку <tex>x</tex> на второй дорожке. Только при таком условии <tex>M</tex> принимает цепочку <tex>x</tex>. Но, по построению, процесс генерации <tex>x</tex> воспроизводит вывод этой цепочки из <tex>S</tex>. Следовательно, <tex>S \Rightarrow^*_M x</tex>.
}}
* Операции, которые могут удалить всё кроме не измененной копии строки. Применяются, когда, симулированная на другой копии исходной строки, последовательность действий <tex>M</tex> привела к принимающему состоянию.
Более подробное доказательство приведено в книге <ref>[http://www.math.spbu.ru/user/mbk/PDF/ Мартыненко Б.К. Языки и трансляцииcтр. 115]</ref>.
}}
== См. также ==
* [[Машина ТьюрингаЛямбда-исчисление]]* [[Иерархия Хомского формальных грамматик#Класс 1|Контекстно-зависимые грамматикиСчетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] == Примечания ==<references/>
== Источники информации ==
