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

Материал из Викиконспекты
Перейти к: навигация, поиск
(См. также)
м (rollbackEdits.php mass rollback)
 
(не показаны 24 промежуточные версии 5 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition = '''Линейно ограниченный автомат''' ''(lba)'' — недетерминированная одноленточная машина Тьюринга, которая никогда не покидает те ячейки, на которых размещен ее ввод.}}
+
|definition = '''Линейно ограниченный автомат''' (англ. ''linear bounded automata'', ''lba'') — недетерминированная одноленточная [[Машина Тьюринга|машина Тьюринга]], которая никогда не покидает те ячейки, на которых размещен ее ввод.}}
  
 
Более формально:
 
Более формально:
 
{{Определение
 
{{Определение
|definition = '''Линейно ограниченный автомат''' ''(lba)'' — формальная система <tex>M = \langle Q, \Sigma, \Gamma, \delta, q_0, F \rangle</tex>, в которой
+
|definition = '''Линейно ограниченный автомат''' — формальная система <tex>M = \langle Q, \Sigma, \Gamma, \delta, q_0, F \rangle</tex>, в которой
*<tex>Q</tex> — множество состояний.
+
*<tex>Q</tex> — множество состояний,
*<tex>q_0 \in Q</tex> — начальное состояние.
+
*<tex>q_0 \in Q</tex> — начальное состояние,
*<tex>F \subset Q</tex> — множество конечных состояний.
+
*<tex>F \subset Q</tex> — множество конечных состояний,
*<tex>\Gamma</tex> — алфавит допустимых символов ленты.
+
*<tex>\Gamma</tex> — алфавит допустимых символов ленты,
*<tex>\Sigma \subset \Gamma</tex> — алфавит входных символов, который содержит два особых символа: <tex>\#</tex> и <tex>\$</tex> — левый и правый маркеры, находящиеся с самого начала на концах входной цепочки для того, чтобы предотвращать выход головки ленты за пределы участка, на котором размещается входная цепочка (считается, что маркеры могут использоваться только в этой роли: на место маркера нельзя записать какой-нибудь другой символ ленты, и никакой символ ленты не может быть заменен каким-нибудь маркером).
+
*<tex>\Sigma \subset \Gamma</tex> — алфавит входных символов, который содержит два особых символа: <tex>\#</tex> и <tex>\$</tex> — левый и правый маркеры, находящиеся с самого начала на концах входной цепочки для того, чтобы предотвращать выход головки ленты за пределы участка, на котором размещается входная цепочка (считается, что маркеры могут использоваться только в этой роли: на место маркера нельзя записать какой-нибудь другой символ ленты, и никакой символ ленты не может быть заменен каким-нибудь маркером),
 
*<tex>\delta</tex> — отображение типа <tex>Q \times \Gamma \to 2^{Q \times \Gamma \times \{\leftarrow, \rightarrow\}}</tex>.}}
 
*<tex>\delta</tex> — отображение типа <tex>Q \times \Gamma \to 2^{Q \times \Gamma \times \{\leftarrow, \rightarrow\}}</tex>.}}
  
 
Из определения следует, что языком, принимаемым линейно ограниченным автоматом <tex>M</tex>, называется множество  
 
Из определения следует, что языком, принимаемым линейно ограниченным автоматом <tex>M</tex>, называется множество  
<tex>\{w|w\in(\Sigma\setminus\{\#,\$\})^*,(q0,\#w\$,1)\vdash^*_M(q,\#\alpha\$,i),q\in F,\alpha \in \Gamma^*</tex><tex>, 1 \le i\le n,n = |w|+2\}.</tex>
+
 
 +
<tex>L(M)=\{w\mid w\in (\Sigma \setminus \{\#, \$\})^*,\ (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>
  
  
Строка 20: Строка 21:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Если <tex>L</tex> — контекстно-зависимый язык, то язык <tex>L</tex> принимается некоторым линейно ограниченным автоматом.  
+
Если <tex>L</tex> — [[Иерархия Хомского формальных грамматик#Класс 1|контекстно-зависимый язык]], то язык <tex>L</tex> принимается некоторым линейно ограниченным автоматом.  
 
|proof=
 
|proof=
Пусть <tex>G = \langle V_N , V_T, P, S\rangle</tex> — контекстно-зависимая грамматика. Мы построим lba <tex>M</tex>, такой, что язык, принимаемый lba <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>M</tex> помещает символ <tex>S</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(\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>x (x \ne \epsilon)</tex> с концевыми маркерами. Вторая дорожка будет использоваться для работы.
 
  
На первом шаге lba <tex>M</tex> помещает символ <tex>S</tex> в крайнюю левую ячейку второй дорожки. Затем автомат входит в порождающую подпрограмму, которая выполняет следующие шаги:
+
{{Теорема
 +
|statement=
 +
Если язык <tex>L</tex> принимается линейно ограниченным автоматом, то <tex>L</tex> — контекстно-зависимый язык.  
 +
|proof=
 +
Доказательство схоже с доказательством [[Возможность порождения формальной грамматикой произвольного перечислимого языка|теоремы о формальной грамматике, генерирующая язык, распознаваемый МТ]].
  
'''1.''' Подпрограмма выбирает последовательные подстроки символов <tex>\alpha</tex> на второй дорожке, такие, что <tex>\alpha \rightarrow \beta \in P</tex>.  
+
Для доказательства этой теоремы построим контекстно-зависимую грамматику, которая моделирует линейно ограниченный автомат.
 +
Нетерминалы контекстно-зависимой грамматики должны указывать не только первоначальное содержание некоторой ячейки ленты линейно ограниченного автомата, но также и то, является ли эта ячейка смежной с концевым маркером слева или справа. Такие ячейки в обозначении нетерминалов мы будем снабжать маркерами <tex>\#</tex> и <tex>\$</tex>, обозначающими, что ячейка граничит соответственно с левым, правым или обоими концевыми маркерами. В обозначении нетерминала состояние линейно ограниченного автомата должно также комбинироваться с символом, находящимся под головкой ленты. Контекстно-зависимая грамматика не может иметь отдельных символов для концевых маркеров и состояния линейно ограниченного автомата, потому что эти символы должны были бы заменяться на пустые цепочки, когда строка превращается в терминальную, а <tex>\varepsilon</tex>-порождения в контекстно-зависимой грамматике запрещены.
  
'''2.''' Подстроки <tex>\alpha</tex> заменяются на <tex>\beta</tex>, сдвигая вправо, если необходимо, символы, расположенные справа от <tex>\alpha</tex>. Если эта операция заставляет символ быть вытолкнутым за правый маркер, автомат останавливается. Как известно, промежуточные сентенциальные формы в контекстно-зависимой грамматике не длиннее, чем выводимая терминальная цепочка. Так что, если на очередном шаге получена строка длиннее x, то продолжать процесс не имеет смысла, потому что все последующие строки будут разве лишь длиннее.  
+
В грамматике необходимо поддерживать три типа операций:
 +
* Операции, которые генерирую две копии строки, наряду с некоторыми символами, которые выполняют роль маркеров, чтобы разделять эти копии.
 +
* Операции, которые симулируют некоторую последовательность действий линейно ограниченного автомата <tex>M</tex>. Во время их выполнения, одна из двух копий оригинальной строки остается неизменной, другая же представляет из себя входную ленту <tex>M</tex> и соответствующе изменяется.
 +
* Операции, которые могут удалить всё кроме не измененной копии строки. Применяются, когда, симулированная на другой копии исходной строки, последовательность действий <tex>M</tex> привела к принимающему состоянию.
  
'''3.''' Подпрограмма недетерминированно выбирает, возвращаться ли к шагу 1, либо идти на выход.
+
Более подробное доказательство приведено в книге<ref>[http://www.math.spbu.ru/user/mbk/PDF/ Мартыненко Б.К. Языки и трансляции cтр. 115]</ref>.
 
   
 
   
'''4.''' При выходе из подпрограммы первая дорожка все еще будет содержать строку <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>, то найдется такая последовательность движений lba <tex>M</tex>, которая сгенерирует цепочку <tex>x</tex> на второй дорожке, и тогда автомат остановится, принимая. Аналогично, если lba <tex>M</tex> принимает цепочку <tex>x</tex>, то должна существовать последовательность движений, генерирующих цепочку <tex>x</tex> на второй дорожке. Только при таком условии lba <tex>M</tex> принимает цепочку <tex>x</tex>. Но, по построению, процесс генерации <tex>x</tex> воспроизводит вывод этой цепочки из <tex>S</tex>. Следовательно, <tex>S \Rightarrow^*_M x</tex>.
 
 
}}
 
}}
  
 
== См. также ==
 
== См. также ==
* [[Машина Тьюринга]]
+
* [[Лямбда-исчисление]]
* [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободные грамматики]]
+
* [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]
 +
 
 +
== Примечания ==
 +
<references/>
 +
 
 +
== Источники информации ==
 +
* [http://drona.csa.iisc.ernet.in/~deepakd/atc-2011/lba.pdf| Linear Bounded Automata]
  
== Литература ==
+
[[Категория: Теория формальных языков]]
* Мартыненко Б.К. Языки и трансляции: Учеб. пособие ISBN 5-288-02870-2
+
[[Категория: Теория вычислимости]]
 +
[[Категория: Вычислительные формализмы]]

Текущая версия на 19:40, 4 сентября 2022

Определение:
Линейно ограниченный автомат (англ. 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]

См. также

Примечания

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