Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
138
И. Хомский
1 4. Автомат с магазинным накопителем (устройство PDS)
Рассмотрим следующий специальный класс линейно-ограиичен-ньіх автоматов, представляющий особый интерес. Пусть автомат M имеет две ленты, одну — входную, другую — ленту памяти. Блок управления может считывать символы с входной ленты и с ленты памяти и записывать символы на ленте памяти. Входная лента может двигаться только в одном направлении, скажем, справа налево. Лента памяти может двигаться в обоих направлениях. Символы входного алфавита А; могут появляться на входной ленте, символы выходного алфавита A0 могут считываться или записываться на ленте памяти; алфавиты Л; и Ao такие же, как выше. Мы предполагаем, что Ao содержит выделенный символ a(Ai , который будет использоваться только в начале и в конце работы устройства; каким способом, будет явно определено ниже. В разд. 1.4— 1.6 единичный элемент алфавитов Ao и Ai обозначается через е вмгето а„. Другие символы Ao мы продолжаем обозначать Oil--Ar Алфавиты Л; и Л о рассматриваются как «универсальные алфавиты», независимые от конкретной машины.
Мы определяем ситуацию машины как тройку (a, S1, Ь), где а — символ, считываемый с входной ленты, Si— состояние блока управления, а Ь — символ, считываемый с ленты памяти. Каждый шаг работы зависит в общем случае от всей ситуации машины.
При начальной конфигурации ленты-машины входная лента содержит символы ар, ,...,ар* (где теперь уже Pi=^O); они записаны в подряд идущих клетках ленты и ограничены с обеих сторон символами #; блок управления находится в состоянии S0 и наблюдает самый левый символ ар, цепочки x—а^...а^ (как па рис. 2). Рассматриваемая клетка ленты памяти содержит о, а все остальные ее клетки содержат #. Таким образом, в начальной конфигурации автомат находится в ситуации (ap, ,S0, #). Автомат продолжает свою работу способом, описанным ниже, до первого возвращения в S0. Входная цепочка х допускается автоматом, если в момент возвращения как на входной ленте, так и на ленте памяти наблюдается символ #, т.е. если автомат находится в заключительной ситуации (#. S0,?).
Специальное свойство этих устройств, отличающее их от линейно-ограниченных автоматов общего вида, заключается в следующем. Когда лента памяти движется на одну клетку вправо, предыдущий рассмотренный символ как бы «стирается». Когда лента памяти движется на k клеток влево, открывая k новых клеток, то в этих клетках записываются последовательно k символов из Ao, все отличные от е. Когда лента не движется, ничто не записывается и ничто He стирается. Поэтому на каждом шаге работы машины только самый правый символ ленты памяти доступен для рассмотрения. Символ, записанный на ленту последним, считывается с нее первым.
Формальные свойства грамматик
139
Следовательно, лента памяти обязательно будет совершенно пуста [blank] (т.е. будет содержать только #), если достигнута заключительная ситуация (#, S0,#).
Устройство М, которое ведет себя описанным выше образом, мы будем, следуя Ньюэллу, Шоу и Саймону [47], называть автоматом с магазинной памятью или автоматом PDS (pushdown storage automaton). Эта система памяти нашла широкое применение в программировании; в частности, многие авторы отмечают, что она весьма полезна при машинном синтякгичргкпм янялизе языка. Причины этой полезности, так же как и ограничения, присущие теории таких автоматов, станут вполне ясны, когда мы увидим, что она представляет собой, в сущности, другой вариант теории бесконтекстных грамматик (ср. разд. 4 предыдущей главы). Отметим, что автомат PDS, возможно с недетерминированным блоком управления, есть тот самый механизм, который выполняет «предсказусмостный анализ» в смысле И. Роудес (см. работу [48]). Следовательно, и эта теория также является в основном вариантом теории бесконтекстных грамматик.
Перейдем теперь к явному определению работы автомата PDS. Мы предполагаем, выбирая одну из двух эквивалентных формулировок, приведенных выше (стр. 127), что е не может появляться ни в клетках входной ленты, ни в клетках ленты памяти. Тогда мы расширяем определение «ситуации» так, чтобы были допустимы тройки (е, Si, b), (a, Si, е) и (в, Sil в), и говорим, что, когда автомат находится в ситуации (a, Si, Ь), он одновременно находится в ситуации (е, Si, b), (a, Si, е) и (в, Si, е), т.е. любая команда, применимая в ситуациях (е, Si, b), (a, S1 , е) и (в, Si, е), будет применима, когда устройство находится в состоянии Si и рассматривает символ а на входной ленте и символ Ь на ленте памяти. Входная лента действительно продвигается влево только тогда, когда применяется команда, содержащая в качестве символа на входной ленте некоторое афе.
Определим функцию Х(х) (читай: «длина х») для некоторых цепочек х следующим образом: M0) =—1; Х(е)=0; Цга^—X(z)-j-l, где га; есть цепочка в алфавите Ao— (°}, (1<?<^(/).
Каждая команда автомата PDS может теперь быть задана в стандартной форме
(a, Si, b) -+ (S,, х), (1)
где a?Ai , Ь?Ао, х—а или х есть цепочка в алфавите A0—1°), a / —О тогда и только тогда, когда 6 = а=х. Команда вида (1) применима, когда механизм находится в ситуации [a, S1, Ь), и ее применение дает следующий результат: блок управления переходит в состояние Sj-, входная лента движется на X (а) клеток влево; символы х печатаются последовательно в клетках, находящихся вправо
