Линейно ограниченный автомат

Определение:

Линейно ограниченный автомат (англ. linear bounded automata, lba) — недетерминированная одноленточная машина Тьюринга, которая никогда не покидает те ячейки, на которых размещен ее ввод.

Более формально:

Определение:

Линейно ограниченный автомат — формальная система [math]M = \langle Q, \Sigma, \Gamma, \delta, q_0, F \rangle[/math], в которой [math]Q[/math] — множество состояний, [math]q_0 \in Q[/math] — начальное состояние, [math]F \subset Q[/math] — множество конечных состояний, [math]\Gamma[/math] — алфавит допустимых символов ленты, [math]\Sigma \subset \Gamma[/math] — алфавит входных символов, который содержит два особых символа: [math]\#[/math] и [math]\$[/math] — левый и правый маркеры, находящиеся с самого начала на концах входной цепочки для того, чтобы предотвращать выход головки ленты за пределы участка, на котором размещается входная цепочка (считается, что маркеры могут использоваться только в этой роли: на место маркера нельзя записать какой-нибудь другой символ ленты, и никакой символ ленты не может быть заменен каким-нибудь маркером), [math]\delta[/math] — отображение типа [math]Q \times \Gamma \to 2^{Q \times \Gamma \times \{\leftarrow, \rightarrow\}}[/math].

Из определения следует, что языком, принимаемым линейно ограниченным автоматом [math]M[/math], называется множество [math]L(M) = \{w \mid w \in (\Sigma \setminus \{\#, \$\})^*,[/math] [math] (q0, \#w\$, 1) \vdash^*_M (q, \#\alpha\$, i), q \in F, \alpha \in \Gamma^*[/math][math], 1 \leqslant i \leqslant n, n = |w| + 2\}.[/math]

Связь линейно ограниченных автоматов с контекстно-зависимыми языками

Теорема:

Если [math]L[/math] — контекстно-зависимый язык, то язык [math]L[/math] принимается некоторым линейно ограниченным автоматом.

Доказательство:

[math]\triangleright[/math]

Пусть [math]G = \langle V_N , V_T, P, S\rangle[/math] — контекстно-зависимая грамматика. Мы построим линейный ограниченный автомат [math]M[/math], такой, что язык, принимаемый [math]M[/math], есть [math]L(G)[/math]. Входная лента будет иметь две дорожки. Первая дорожка будет содержать входную строку [math]x (x \ne \varepsilon)[/math] с концевыми маркерами. Вторая дорожка будет использоваться для работы. На первом шаге [math]M[/math] помещает символ [math]S[/math] в крайнюю левую ячейку второй дорожки. Затем автомат входит в порождающую подпрограмму, которая выполняет следующие шаги: Подпрограмма выбирает последовательные подстроки символов [math]\alpha[/math] на второй дорожке, такие, что [math]\alpha \rightarrow \beta \in P[/math]. Подстроки [math]\alpha[/math] заменяются на [math]\beta[/math], сдвигая вправо, если необходимо, символы, расположенные справа от [math]\alpha[/math]. Если эта операция заставляет символ быть вытолкнутым за правый маркер, автомат останавливается. Как известно, промежуточные сентенциальные формы в контекстно-зависимой грамматике не длиннее, чем выводимая терминальная цепочка. Так что, если на очередном шаге получена строка длиннее x, то продолжать процесс не имеет смысла, потому что все последующие строки будут разве лишь длиннее. Подпрограмма недетерминированно выбирает, возвращаться ли к шагу 1, либо идти на выход. При выходе из подпрограммы первая дорожка все еще будет содержать строку [math]x[/math], в то время как вторая дорожка будет содержать некоторую строку [math]y[/math], такую, что [math]S \Rightarrow^*_M y[/math]. Автомат [math]M[/math] сравнивает посимвольно цепочки [math]x[/math] и [math]y[/math]. Если окажется, что [math]x \ne y[/math], то автомат останавливается, не принимая, если же окажется, что [math]x = y[/math], то он останавливается, принимая входную цепочку. Ясно, что если [math]x \in L(G)[/math], то найдется такая последовательность движений [math]M[/math], которая сгенерирует цепочку [math]x[/math] на второй дорожке, и тогда автомат остановится, принимая. Аналогично, если [math]M[/math] принимает цепочку [math]x[/math], то должна существовать последовательность движений, генерирующих цепочку [math]x[/math] на второй дорожке. Только при таком условии [math]M[/math] принимает цепочку [math]x[/math]. Но, по построению, процесс генерации [math]x[/math] воспроизводит вывод этой цепочки из [math]S[/math]. Следовательно, [math]S \Rightarrow^*_M x[/math].

[math]\triangleleft[/math]

Теорема:

Если язык [math]L[/math] принимается линейно ограниченным автоматом, то [math]L[/math] — контекстно-зависимый язык.

Доказательство:

[math]\triangleright[/math]

Доказательство схоже с доказательством теоремы о формальной грамматике, генерирующая язык, распознаваемый МТ. Для доказательства этой теоремы построим контекстно-зависимую грамматику, которая моделирует линейно ограниченный автомат. Нетерминалы контекстно-зависимой грамматики должны указывать не только первоначальное содержание некоторой ячейки ленты линейно ограниченного автомата, но также и то, является ли эта ячейка смежной с концевым маркером слева или справа. Такие ячейки в обозначении нетерминалов мы будем снабжать маркерами [math]\#[/math] и [math]\$[/math], обозначающими, что ячейка граничит соответственно с левым, правым или обоими концевыми маркерами. В обозначении нетерминала состояние линейно ограниченного автомата должно также комбинироваться с символом, находящимся под головкой ленты. Контекстно-зависимая грамматика не может иметь отдельных символов для концевых маркеров и состояния линейно ограниченного автомата, потому что эти символы должны были бы заменяться на пустые цепочки, когда строка превращается в терминальную, а [math]\varepsilon[/math]-порождения в контекстно-зависимой грамматике запрещены. В грамматике необходимо поддерживать три типа операций: Операции, которые генерирую две копии строки, наряду с некоторыми символами, которые выполняют роль маркеров, чтобы разделять эти копии. Операции, которые симулируют некоторую последовательность действий линейно ограниченного автомата [math]M[/math]. Во время их выполнения, одна из двух копий оригинальной строки остается неизменной, другая же представляет из себя входную ленту [math]M[/math] и соответствующе изменяется. Операции, которые могут удалить всё кроме не измененной копии строки. Применяются, когда, симулированная на другой копии исходной строки, последовательность действий [math]M[/math] привела к принимающему состоянию. Более подробное доказательство приведено в книге Мартыненко Б.К. Языки и трансляции.

[math]\triangleleft[/math]

См. также

• Машина Тьюринга
• Контекстно-зависимые грамматики

Ссылки

http://drona.csa.iisc.ernet.in/~deepakd/atc-2011/lba.pdf

Литература

• Мартыненко Б.К. Языки и трансляции: Учеб. пособие ISBN 5-288-02870-2