Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
142
Н. Хомский
(а) (a, S0, е) (Si, а),
(б) (а, Sv е) -> (S1, а).
(в) (с, S1, (.) -»¦ (S2, е),
(г) (а, S2, а) (S2, о),
(д) (е, S2, о) -> (S0, о).
Блок управления имеет диаграмму состояний, показанную на рис. 6, где тройка (г, S1 t) помечает стрелку, ведущую от состояния Si к состоянию Sj тогда и только тогда, когда имеется правило (г, S1, s)->(Sy, t). Очевидно, что это устройство допускает цепочку тогда и только тоща, когда она принадлежит языку V2. Например, последовательные шаги работы при порождении цепочки #abcbaif показаны на рис. 7.
Очевидно, устройство PDS очень хорошо подходит для порождения таких языков, как L2', которые в каком-то смысле имеют единицы (фразы), вложенные друг в друга, т.е. что-то вроде рекурсивного свойства, названного нами в предыдущей главе (разд. 3) самовставлением. В разд. 4.2 и 4.6 мы увидим, что основное свойство бесконтекстных грамматик (ср. с предыдущей главой, разд. 4), отличающее их от конечных автоматов, состоит в том, что они допускают самовставление и симметрии в порождаемых цепочках. Следовательно, можно ожидать, что устройства с магазинной памятью будут полезны при построении языков с грамматиками такого типа. Этот класс, очевидно, содержит многие известные искусственные языки (например, язык исчисления высказываний и, возможно, также многие языки программирования — см. разд. 4.8). Действительно, весьма нетрудно построить автомат PDS, который будет распознавать или порождать предложения в таких системах. Эттингер [48] указывает, что если оборудовать устройство PDS дополнительной выходной лентой и переделать его команды так, чтобы оно могло отображать входную цепочку на соответственную выходную (используя при работе свою магазинную память), то можно заставить его, например, переводить формулы из обычной скобочной записи в бесскобочную запись Лукасевича и обратно. В некотором приближении бесконтекстные грамматики непосредственных составляющих частично адекватны естественным языкам; вложенные фразы (самовставление) и симметрии составляют одно из основных свойств естественного языка. Поэтому такие устройства, как PDS, будут полезны при решении различных задач автоматической обработки текстов на естественных языках.
Устройство PDS с правилами (2) является детерминированным. В случае конечных автоматов мы видим (теорема 1), что для каждого конечного автомата существует эквивалентный ему детерминиро-
(Є, б, б)
Рис. 6. Диаграмма состояний для М.
•••И* а й№1ФН 1*1*1а й cH«kl*l 1*1*И» с »!«1*1*1 ••
IXl
Начальная позиция
# * o 6ciа *f
ц*\б\а
Позиция 3
m
Позиция 1
а ¦И-
ш
•••1*1Ф а 6H
* ’ * МФНФк * ¦
I sQ I
...|+ tfHsH
• - * 1*1* б ¦И —1*1Ф а *|#|... —1+1*!«!»
Позиция г
• м*|ф|с№ * *]
Позиция 5
Позиция 6
P и с. 7. Порождение цепочки ttabcba# устройством PDS
144
Н. Хомский
ванный автомат. Однако для автоматов PDS это не имеет места. Так, не существует детерминированного автомата PDS, который допускал бы язык L2= [хх*\х* есть зеркальное отражение х) (т.е. I состоит из цепочек, которые получаются, если выбросить средний элемент с из цепочек языка L2'), поскольку он никак не сможет узнать, когда достигается середина входной цепочки; однако Ii порождается недетерминированным автоматом PDS, отличающимся от устройства (2) для L2' заменой правила (в) правилом (я, S1, е) -> (S2, а). (3)
Эго сводится к выбрасыванию стрелки (с, е, в).на рис. 6 и соединению состояний S1 и S2 двумя стрелками, одна из которых помечена (а,е,а), а другая—(Ь,е,Ь). Устройство применяет команду (3) тогда, когда оно «делает предположение» о том, что достигнута середина цепочки. Если это предположение не оправдывается, то работа устройства не может закончиться допущением цепочки (точно так же, как если бы входная цепочка не принадлежала языку Li); если предположение оправдывается и входная цепочка принадлежит языку L2, то работа устройства закончится допущением цг-почки.
Мы допустили здесь, что следующий шаг работы устройства частично определяется символом, считываемым с ленты памяти. Интересно изучить вопрос о том, насколько контроль со стороны ленты памяти существен для устройства PDS. Рассмотрим два подкласса автоматов PDS, заданные следующими условиями: M есть автомат PDS без контроля, если каждое правило его имеет вид (a, Sh e)-+(Sj,x); M есть автомат PDS с ограниченным контролем, если каждое его правило имеет либо вид (a, Si, e)->(Sy, х), хфа, либо вид (a, Sil b)-*-(Sj, о). Иначе говоря, в автоматах с ограниченным контролем символ, считываемый с ленты памяти, играет роль только при определении тех шагов, при которых происходит стирание с ленты памяти. Мы видим, что устройство на рис. 6 имеет ограниченный контроль. В случае устройства PDS без контроля лента памяти работает лишь как счетчик. Без ограничения общности можно полагать, что ее алфавит содержит лишь один символ. Рассматривая эти семейства автоматов, мы приходим к следующей теореме.
T е о р е м а 4. (а) Семейство автоматов PDS без контроля имеет порождающую способность существенно большую, чем семейство конечных автоматов, но существенно меньшую, чем все семейство устройств PDS. (б) Для каждого устройства PDS существует эквивалентное ему устройство PDS с ограниченным, контролем.
