Линейно ограниченный автомат — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Связь линейно ограниченных автоматов с контекстно-зависимыми языками)
Строка 23: Строка 23:
 
Если <tex>L</tex> — [[Иерархия Хомского формальных грамматик#Класс 1|контекстно-зависимый язык]], то язык <tex>L</tex> принимается некоторым линейно ограниченным автоматом.  
 
Если <tex>L</tex> — [[Иерархия Хомского формальных грамматик#Класс 1|контекстно-зависимый язык]], то язык <tex>L</tex> принимается некоторым линейно ограниченным автоматом.  
 
|proof=
 
|proof=
Пусть <tex>G = \langle \Sigma , N, S, P\rangle</tex> — контекстно-зависимая грамматика. Мы построим линейный ограниченный автомат <tex>M</tex>, такой, что язык, принимаемый <tex>M</tex>, есть <tex>L(G)</tex>.  
+
Пусть <tex>\Gamma = \langle \Sigma , N, S, P\rangle</tex> — контекстно-зависимая грамматика. Мы построим линейный ограниченный автомат <tex>M</tex>, такой, что язык, принимаемый <tex>M</tex>, есть <tex>L(\Gamma)</tex>.  
  
 
Входная лента будет иметь две дорожки. Первая дорожка будет содержать входную строку <tex>x (x \ne \varepsilon)</tex> с концевыми маркерами. Вторая дорожка будет использоваться для работы.  
 
Входная лента будет иметь две дорожки. Первая дорожка будет содержать входную строку <tex>x (x \ne \varepsilon)</tex> с концевыми маркерами. Вторая дорожка будет использоваться для работы.  
Строка 34: Строка 34:
 
#При выходе из подпрограммы первая дорожка все еще будет содержать строку <tex>x</tex>, в то время как вторая дорожка будет содержать некоторую строку <tex>y</tex>, такую, что <tex>S \Rightarrow^*_M y</tex>.  
 
#При выходе из подпрограммы первая дорожка все еще будет содержать строку <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)</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> сравнивает посимвольно цепочки <tex>x</tex> и <tex>y</tex>. Если окажется, что <tex>x \ne y</tex>, то автомат останавливается, не принимая, если же окажется, что <tex>x = y</tex>, то он останавливается, принимая входную цепочку. Ясно, что если <tex>x \in L(\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>.  
 
}}
 
}}
  

Версия 00:51, 7 января 2015

Определение:
Линейно ограниченный автомат (англ. 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 \{\#, \$\})^*,\ (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]\Gamma = \langle \Sigma , N, S, P\rangle[/math] — контекстно-зависимая грамматика. Мы построим линейный ограниченный автомат [math]M[/math], такой, что язык, принимаемый [math]M[/math], есть [math]L(\Gamma)[/math].

Входная лента будет иметь две дорожки. Первая дорожка будет содержать входную строку [math]x (x \ne \varepsilon)[/math] с концевыми маркерами. Вторая дорожка будет использоваться для работы.

На первом шаге [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]. Если эта операция заставляет символ быть вытолкнутым за правый маркер, автомат останавливается. Как известно, промежуточные сентенциальные формы в контекстно-зависимой грамматике не длиннее, чем выводимая терминальная цепочка. Так что, если на очередном шаге получена строка длиннее [math]x[/math], то продолжать процесс не имеет смысла, потому что все последующие строки будут разве лишь длиннее.
  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(\Gamma )[/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] привела к принимающему состоянию.
Более подробное доказательство приведено в книге[1].
[math]\triangleleft[/math]

См. также

Примечания

Источники информации