Линейно ограниченный автомат — различия между версиями
(→Источники информации) |
м (rollbackEdits.php mass rollback) |
||
(не показано 14 промежуточных версий 5 участников) | |||
Строка 13: | Строка 13: | ||
Из определения следует, что языком, принимаемым линейно ограниченным автоматом <tex>M</tex>, называется множество | Из определения следует, что языком, принимаемым линейно ограниченным автоматом <tex>M</tex>, называется множество | ||
− | <tex>L(M) = \{w \mid w \in (\Sigma \setminus \{\#, \$\})^*, | + | |
+ | <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> | ||
Строка 22: | Строка 23: | ||
Если <tex>L</tex> — [[Иерархия Хомского формальных грамматик#Класс 1|контекстно-зависимый язык]], то язык <tex>L</tex> принимается некоторым линейно ограниченным автоматом. | Если <tex>L</tex> — [[Иерархия Хомского формальных грамматик#Класс 1|контекстно-зависимый язык]], то язык <tex>L</tex> принимается некоторым линейно ограниченным автоматом. | ||
|proof= | |proof= | ||
− | Пусть <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> с концевыми маркерами. Вторая дорожка будет использоваться для работы. | ||
Строка 29: | Строка 30: | ||
#Подпрограмма выбирает последовательные подстроки символов <tex>\alpha</tex> на второй дорожке, такие, что <tex>\alpha \rightarrow \beta \in P</tex>. | #Подпрограмма выбирает последовательные подстроки символов <tex>\alpha</tex> на второй дорожке, такие, что <tex>\alpha \rightarrow \beta \in P</tex>. | ||
− | #Подстроки <tex>\alpha</tex> заменяются на <tex>\beta</tex>, сдвигая вправо, если необходимо, символы, расположенные справа от <tex>\alpha</tex>. Если эта операция заставляет символ быть вытолкнутым за правый маркер, автомат останавливается. Как известно, промежуточные сентенциальные формы в контекстно-зависимой грамматике не длиннее, чем выводимая терминальная цепочка. Так что, если на очередном шаге получена строка длиннее x, то продолжать процесс не имеет смысла, потому что все последующие строки будут разве лишь длиннее. | + | #Подстроки <tex>\alpha</tex> заменяются на <tex>\beta</tex>, сдвигая вправо, если необходимо, символы, расположенные справа от <tex>\alpha</tex>. Если эта операция заставляет символ быть вытолкнутым за правый маркер, автомат останавливается. Как известно, промежуточные сентенциальные формы в контекстно-зависимой грамматике не длиннее, чем выводимая терминальная цепочка. Так что, если на очередном шаге получена строка длиннее <tex>x</tex>, то продолжать процесс не имеет смысла, потому что все последующие строки будут разве лишь длиннее. |
#Подпрограмма недетерминированно выбирает, возвращаться ли к шагу 1, либо идти на выход. | #Подпрограмма недетерминированно выбирает, возвращаться ли к шагу 1, либо идти на выход. | ||
#При выходе из подпрограммы первая дорожка все еще будет содержать строку <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( | + | Автомат <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>. |
}} | }} | ||
Строка 51: | Строка 52: | ||
* Операции, которые могут удалить всё кроме не измененной копии строки. Применяются, когда, симулированная на другой копии исходной строки, последовательность действий <tex>M</tex> привела к принимающему состоянию. | * Операции, которые могут удалить всё кроме не измененной копии строки. Применяются, когда, симулированная на другой копии исходной строки, последовательность действий <tex>M</tex> привела к принимающему состоянию. | ||
− | Более подробное доказательство приведено в книге Мартыненко Б.К. Языки и трансляции. | + | Более подробное доказательство приведено в книге<ref>[http://www.math.spbu.ru/user/mbk/PDF/ Мартыненко Б.К. Языки и трансляции cтр. 115]</ref>. |
+ | |||
}} | }} | ||
== См. также == | == См. также == | ||
− | * [[ | + | * [[Лямбда-исчисление]] |
− | * [[ | + | * [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] |
+ | |||
+ | == Примечания == | ||
+ | <references/> | ||
== Источники информации == | == Источники информации == | ||
− | + | * [http://drona.csa.iisc.ernet.in/~deepakd/atc-2011/lba.pdf| Linear Bounded Automata] | |
− | * [http://drona.csa.iisc.ernet.in/~deepakd/atc-2011/lba.pdf|Linear Bounded Automata | + | |
+ | [[Категория: Теория формальных языков]] | ||
+ | [[Категория: Теория вычислимости]] | ||
+ | [[Категория: Вычислительные формализмы]] |
Текущая версия на 19:40, 4 сентября 2022
Определение: |
Линейно ограниченный автомат (англ. linear bounded automata, lba) — недетерминированная одноленточная машина Тьюринга, которая никогда не покидает те ячейки, на которых размещен ее ввод. |
Более формально:
Определение: |
Линейно ограниченный автомат — формальная система
| , в которой
Из определения следует, что языком, принимаемым линейно ограниченным автоматом , называется множество
Содержание
Связь линейно ограниченных автоматов с контекстно-зависимыми языками
Теорема: |
Если контекстно-зависимый язык, то язык принимается некоторым линейно ограниченным автоматом. — |
Доказательство: |
Пусть — контекстно-зависимая грамматика. Мы построим линейный ограниченный автомат , такой, что язык, принимаемый , есть .Входная лента будет иметь две дорожки. Первая дорожка будет содержать входную строку с концевыми маркерами. Вторая дорожка будет использоваться для работы.На первом шаге помещает символ в крайнюю левую ячейку второй дорожки. Затем автомат входит в порождающую подпрограмму, которая выполняет следующие шаги:
|
Теорема: |
Если язык принимается линейно ограниченным автоматом, то — контекстно-зависимый язык. |
Доказательство: |
Доказательство схоже с доказательством теоремы о формальной грамматике, генерирующая язык, распознаваемый МТ. Для доказательства этой теоремы построим контекстно-зависимую грамматику, которая моделирует линейно ограниченный автомат. Нетерминалы контекстно-зависимой грамматики должны указывать не только первоначальное содержание некоторой ячейки ленты линейно ограниченного автомата, но также и то, является ли эта ячейка смежной с концевым маркером слева или справа. Такие ячейки в обозначении нетерминалов мы будем снабжать маркерами и , обозначающими, что ячейка граничит соответственно с левым, правым или обоими концевыми маркерами. В обозначении нетерминала состояние линейно ограниченного автомата должно также комбинироваться с символом, находящимся под головкой ленты. Контекстно-зависимая грамматика не может иметь отдельных символов для концевых маркеров и состояния линейно ограниченного автомата, потому что эти символы должны были бы заменяться на пустые цепочки, когда строка превращается в терминальную, а -порождения в контекстно-зависимой грамматике запрещены.В грамматике необходимо поддерживать три типа операций:
|