Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Предположим теперь, что мы сняли требование, чтобы лента всегда двигалась влево при переходе из состояния в состояние.
1J Cm. сноску 2 настр. 121.—Прим. fed.
136
И. Хомский
Вместо этого допустим, что направление движения ленты определяется, так же как и следующее состояние, текущим состоянием и считываемым символом. Поведение такого автомата можно описать множеством четверок (i, I, k, I), где t, \, k суть, как и раньше, индексы соответствующей буквы, одного состояния и другого состояния, а / есть одно из ( + 1, 0, —1). Следуя Рабину и Скотту [53], можно интерпретировать эти четверки следующим образом.
J Определение 4. Пусть (і, j, k, I) — одно из правил, определяющих работу автомата М. Если его блок управления находится в состоянии Sj, а его считывающая головка стоит против клетки, содержащей символ аь то блок управления может перейти в состояние Sk, в то время как лента продвигается на I клеток влево. Такое устройство называется двусторонним автоматом.
Будем рассматривать продвижение на —1 клетку влево как продвижение на одну клетку вправо.
Можно снова сказать, что подобный механизмдопускает (порождает) цепочку, точно так же как это делает конечный автомат. А именно он допускает цепочку х только при следующем условии. Пусть цепочка х записана в подряд идущих клетках ленты, а остальные клетки заняты символом #. Пусть блок управления находится в состоянии S0, а считывающая головка стоит против самой левой клетки, не содержащей #. Предположим, что работа автомата продолжается до первого возврата в S0, и в этот момент считывающая головка стоит против клетки с символом it. В этом случае считается, что автомат допускает цепочку х.
Можно было бы ожидать, что, ослабив требования, которым должен удовлетворять конечный автомат, мы увеличили его порождающую способность. Однако дело обстоит не так, и мы имеем следующую теорему [53,73].
Теорема 3. Множества порождаемые двусторонними автоматами, также являются регулярными языками.
Основная идея доказательства состоит в том, что автомат может избавить себя от необходимости возвращаться второй раз на любой Данный участок ленты, если он, до того как покинуть этот участок, «подумает» обо всех вопросах, которые могут быть заданы в дальнейшем (их число должно быть конечно), тут же «ответит» на эги вопросы и «унесет» с собой таблицу вопросов и ответов, двигаясь вперед вдоль ленты и изменяя ответы, если это понадобится. Этот способ дает возможность построения эквивалентного одностороннего автомата, хотя и ценой увеличения числа внутренних состояний блока управления.
Формальные свойства грамматик
137
1.3. Линейно-ограниченные автоматы
Предположим, что двустороннему автомату разрешается писать символы на ленте при переходах из состояния в состояние. Символы, написанные на ленте, принадлежат выходному алфавиту A0 — = {а„,...,ар,...,а11\ (#|Л0), где Ai= {а„,...,ар\ является входным алфавитом. Чтобы описать работу автомата, нам теперь понадобится множество пятерок (i, /, k, /, т), где четверка (i. /, k, I) определяет двусторонний автомат, а рассматриваемый символ Oi заменяется на ат (который, разумеется, может и совпадать с ог), когда автомат переходит из состояния Sj в состояние Sk. Следуя в основных чертах Майхиллу [441, имеем следующее определение.
v Определение 5. Пусть (i, /, k, I, т) — одно из правил, определяющих работу автомата М. Если его блок управления находится в состоянии Sj-, а его считывающая головка стоит против клетки, содержащей символ a[t то блок управления может перейти в состояние Sk, в то время как лечта продвигается на I клеток влево, а рассматриваемый символ а, заменяется на ат. Такое устройство называется линейно-ограниченным автоматом.
Допустимость цепочки определяется так же, как и выше. В лн-нейио-ограниченном автомате лента используется не только в качестве входа, но и в качестве памяти. Действительно, если такой автомат M имеет на входе заданную цепочку х, то в его распоряжении имеется память, объем которой определен числом A(x) + q, где q— заданная память блока управления, с — константа (зависящая от мощности выходного алфавита), а Цх) — длина цепочки х. Следовательно, он является простым потенциально бесконечным автоматом и, как мы увидим далее, может порождать и нерегулярные языки.
При изучении поведения автомата иногда оказывается удобным в целях наглядности приписать ему некоторую дополнительную более сложную структуру. Так, можно рассматривать какое-либо устройство как состоящее из отдельных частей, воплощающих различные аспекты его поведения. В частности, можно считать, что линейно-ограниченный автомат имеет две отдельные бесконечные ленты, одну исключительно для входа, другую — рабочую, причем на второй ленте имеется ровно столько клеток, доступных для записи, сколько занято символами входного алфавита (но не символом +1) на входной ленте. Можно также считать, что имеется несколько независимых рабочих лент этого вида. Этн модификации требуют соответственного изменения списания работы блока управления, но их нетрудно описать таким образом, чтобы порождающая способность рассматриваемого класса автоматов осталась прежней.
