начальное состояние, D- отображение из

Q - это множество состояний,

- множество заключительных состояний,

- множество ленточных символов,

- множество входных символов,

- начальное состояние, D- отображение из Q x ? в подмножество Q x ? x {L, R}.

? содержит два специальных символа, обычно обозначаемых © и $, - левый и правый концевые маркеры, соответственно. Эти символы располагаются сначала по концам входа и их функция - предотвратить переход головки за пределы области, в которой расположен вход.

Конфигурация M и отношение

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

(q,A1A2,...,An,i) где

-целое от 1 до n. Предположим, что

и i > 1

Будем говорить, что

и i < n, будем говорить, что

То есть M печатает A поверх Ai, меняет состояние на p и передвигает головку влево или вправо, но не за пределы области, в которой символы располагались исходно. Как обычно, определим отношение

как

и

Если

,

то

Язык, допускаемый M - это

для некоторого

и целого i}.

Будем называть M детерминированным, если D(q, A) содержит не более одного элемента для любых

. Не известно, совпадает ли класс множеств, допускаемых детерминированными и недетеминированными ЛОА. Ясно, что любое множество, допускаемое недетерминированным ЛОА, допускается некоторой детерминированной МТ. Однако, число ячеек ленты, требуемой этой МТ, может экспоненциально зависеть от длины входа.

Класс множеств, допускаемых ЛОА, в точности совпадает с классом контекстно - зависимых языков.

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

Доказательство. Пусть G = (VN, VT, P, S) - контекстно- зависимая грамматика. Построим ЛОА M такой, что он допускает язык L(G). Не вдаваясь в детали построения M, поскольку он довольно сложен, рассмотрим схему его работы. В качестве ленточных символов будем рассматривать пары

В начальной конфигурации лента содержит (@, B), (a1, B), ... (an, B), ($, B), где a1 ... an = w - входная цепочка, n=|w|.

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