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

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

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

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

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

Линейно ограниченный автомат (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]\{w|w\in(\Sigma\setminus\{\#,\$\})^*,(q0,\#w\$,1)\vdash^*_M(q,\#\alpha\$,i),q\in F,\alpha \in \Gamma^*[/math][math], 1 \le i\le 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] — контекстно-зависимая грамматика. Мы построим lba [math]M[/math], такой, что язык, принимаемый lba [math]M[/math], есть [math]L(G)[/math]. Входная лента будет иметь две дорожки. Первая дорожка будет содержать входную строку [math]x (x \ne \epsilon)[/math] с концевыми маркерами. Вторая дорожка будет использоваться для работы. На первом шаге lba [math]M[/math] помещает символ [math]S[/math] в крайнюю левую ячейку второй дорожки. Затем автомат входит в порождающую подпрограмму, которая выполняет следующие шаги: 1. Подпрограмма выбирает последовательные подстроки символов [math]\alpha[/math] на второй дорожке, такие, что [math]\alpha \rightarrow \beta \in P[/math]. 2. Подстроки [math]\alpha[/math] заменяются на [math]\beta[/math], сдвигая вправо, если необходимо, символы, расположенные справа от [math]\alpha[/math]. Если эта операция заставляет символ быть вытолкнутым за правый маркер, автомат останавливается. Как известно, промежуточные сентенциальные формы в контекстно-зависимой грамматике не длиннее, чем выводимая терминальная цепочка. Так что, если на очередном шаге получена строка длиннее x, то продолжать процесс не имеет смысла, потому что все последующие строки будут разве лишь длиннее. 3. Подпрограмма недетерминированно выбирает, возвращаться ли к шагу 1, либо идти на выход. 4. При выходе из подпрограммы первая дорожка все еще будет содержать строку [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], то найдется такая последовательность движений lba [math]M[/math], которая сгенерирует цепочку [math]x[/math] на второй дорожке, и тогда автомат остановится, принимая. Аналогично, если lba [math]M[/math] принимает цепочку [math]x[/math], то должна существовать последовательность движений, генерирующих цепочку [math]x[/math] на второй дорожке. Только при таком условии lba [math]M[/math] принимает цепочку [math]x[/math]. Но, по построению, процесс генерации [math]x[/math] воспроизводит вывод этой цепочки из [math]S[/math]. Следовательно, [math]S \Rightarrow^*_M x[/math].

[math]\triangleleft[/math]

См. также

• Машина Тьюринга