Викиконспекты - Вклад участника [ru]

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

2020-06-10T22:12:33Z

Adamant: Adamant переименовал страницу Линейный ограниченный автомат в Линейно ограниченный автомат: В соответствии с преамбулой

{{Определение
|definition = '''Линейно ограниченный автомат''' (англ. ''linear bounded automata'', ''lba'') — недетерминированная одноленточная [[Машина Тьюринга|машина Тьюринга]], которая никогда не покидает те ячейки, на которых размещен ее ввод.}}

Более формально:
{{Определение
|definition = '''Линейно ограниченный автомат''' — формальная система <tex>M = \langle Q, \Sigma, \Gamma, \delta, q_0, F \rangle</tex>, в которой
*<tex>Q</tex> — множество состояний,
*<tex>q_0 \in Q</tex> — начальное состояние,
*<tex>F \subset Q</tex> — множество конечных состояний,
*<tex>\Gamma</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>M</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>

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

{{Теорема
|statement=
Если <tex>L</tex> — [[Иерархия Хомского формальных грамматик#Класс 1|контекстно-зависимый язык]], то язык <tex>L</tex> принимается некоторым линейно ограниченным автоматом.
|proof=
Пусть <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>.
}}

{{Теорема
|statement=
Если язык <tex>L</tex> принимается линейно ограниченным автоматом, то <tex>L</tex> — контекстно-зависимый язык.
|proof=
Доказательство схоже с доказательством [[Возможность порождения формальной грамматикой произвольного перечислимого языка|теоремы о формальной грамматике, генерирующая язык, распознаваемый МТ]].

Для доказательства этой теоремы построим контекстно-зависимую грамматику, которая моделирует линейно ограниченный автомат.
Нетерминалы контекстно-зависимой грамматики должны указывать не только первоначальное содержание некоторой ячейки ленты линейно ограниченного автомата, но также и то, является ли эта ячейка смежной с концевым маркером слева или справа. Такие ячейки в обозначении нетерминалов мы будем снабжать маркерами <tex>\#</tex> и <tex>\$</tex>, обозначающими, что ячейка граничит соответственно с левым, правым или обоими концевыми маркерами. В обозначении нетерминала состояние линейно ограниченного автомата должно также комбинироваться с символом, находящимся под головкой ленты. Контекстно-зависимая грамматика не может иметь отдельных символов для концевых маркеров и состояния линейно ограниченного автомата, потому что эти символы должны были бы заменяться на пустые цепочки, когда строка превращается в терминальную, а <tex>\varepsilon</tex>-порождения в контекстно-зависимой грамматике запрещены.

В грамматике необходимо поддерживать три типа операций:
* Операции, которые генерирую две копии строки, наряду с некоторыми символами, которые выполняют роль маркеров, чтобы разделять эти копии.
* Операции, которые симулируют некоторую последовательность действий линейно ограниченного автомата <tex>M</tex>. Во время их выполнения, одна из двух копий оригинальной строки остается неизменной, другая же представляет из себя входную ленту <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]

[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Вычислительные формализмы]]

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

2020-06-10T22:12:33Z

#перенаправление [[Линейно ограниченный автомат]]

Граф блоков-точек сочленения

2020-05-24T17:11:49Z

Adamant: Возврат доказательства, с исправлением

{{Определение
|definition=
Пусть [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|граф]] <tex>G</tex> связен. Обозначим <tex>A_1...A_n</tex> {{---}} блоки, а <tex>a_1...a_m</tex> {{---}} [[Точка сочленения, эквивалентные определения|точки сочленения]] <tex>G</tex>.
Построим двудольный граф <tex>T</tex>, поместив <tex>A_1...A_n</tex> и <tex>a_1...a_m</tex> в различные его доли. Если точка сочленения принадлежит блоку, проведем между ними ребро. Полученный граф <tex>T</tex> называют '''графом блоков-точек сочленения''' ''(англ. block cutpoint graph)'' графа <tex>G</tex>.
}}
<div class="tleft" style="clear:none">[[Файл:block_cut_vertex_1.png|thumb|250px|Граф <tex>G</tex>]]</div>
<div class="tleft" style="clear:none">[[Файл:block_cut_vertex_2.png|thumb|135px|Граф <tex>T</tex>]]</div>
<br>
{{Лемма
|id=lemma1
|statement=
В определении, приведенном выше, <tex>T</tex> {{---}} [[Дерево, эквивалентные определения|дерево]].
|proof=
Достаточно показать, что в <tex>T</tex> нет циклов.
Пусть <tex>A_i, a_k, A_j: a_k \in A_i, A_j</tex> {{---}} последовательные вершины <tex>T</tex>, лежащие на цикле. Тогда существует последовательность точек сочленения и блоков, соединяющая <tex>A_i</tex> и <tex>A_j</tex> и не содержащая <tex>a_k</tex>. По ней можно проложить путь в <tex>G</tex> (можем переходить из блока в блок по точке сочленения и из одной части блока в другую) и замкнуть его в вершине <tex>a_k</tex>, получив цикл. Получается, что некоторые рёбра из <tex>A_i</tex> и <tex>A_j</tex> принадлежат одному и тому же циклу, что противоречит тому, что они находятся в разных блоках.
}}

==См. также==
* [[Граф компонент реберной двусвязности]]

==Источники информации==
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Связность в графах]]

Граф блоков-точек сочленения

2020-05-24T17:07:58Z

Adamant: Через точки сочленения могут проходить циклы. Доказательство неверное.