Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
140
Н. Хомский
от клетки, рассматривавшейся в предыдущий момент на ленте па-мяти (в частности, если х=а,\ то aih помещается в k-й клет-
ке справа от клетки, рассматривавшейся в предыдущий момент, замещая содержимое этой клетки), в то время как лента памяти движется на Цх) клеток влево. Таким образом, если хфа, то теперь устройство будет стоять (иа ленте памяти) против самого правого символа цепочки х; если х—е, то оно останется против 6; если х=о, то оно будет стоять против клетки слева от Ь. Далее, мы полагаем, что содержимое каждой клетки ленты памяти правее рассматриваемой клетки автоматически «стирается» (т.е. заменяется на #). В каждый данный момент мы определяем содержимое леиты памяти как цепочку, стоящую влево от рассматриваемого символа (включая и его), и говорим, что лента памяти содержит эту цепочку. Точнее, если цепочка # ---*?, записана в подряд идущих
клетках ленты памяти, причем арп занимает рассматриваемую клетку, то цепочка Qp1...ар„ есть содержимое ленты памяти. Если рассматриваемый символ ленты памяти есть 4t, мы говорим, что лента содержит цепочку е (ее содержимое есть е) или -лента пуста.
Отметим, что когда автомат M применяет команду (1), входная лента движется на одну клетку влево, если афе, и не движется, если а=е. Далее, если M наблюдает # на входной ленте, команда (1) применима, только если а=е. Из условия «/=0 тогда и только тогда, когда Ь= я ^xn вытекает, что если M начинает работу из начальной конфигурации, то при первом возвращении в S0 оно непременно окажется в ситуации (a, S01 #) при некотором а. Если а=#, автомат M находится в заключительной ситуации, наблюдая # на входной ленте и на ленте памяти, и, следовательно, допускает цепочку, записанную на входной ленте при начальной конфигурации.
В действительности может еще встретиться работа «вхолостую», если имеется команда вида (1) а=е=Ь и І=0, но это не повлияет на порождающую способность устройства. Мы можем считать, что устройство блокировано, когда оно достигает заключительной ситуации. Его лента памяти будет пуста на этом и только на этом шаге работы.
Можно дать более простую характеристику семейства языков, допускаемых автоматами PDS1 не ссылаясь явно на манипуляции с лентами и т.п. Если заданы алфавиты Ai и Ao и символы о, определим автомат PDS M как конечное множество команд вида (1). Для каждого і пусть будет а-а=е, т.е. о является «правым обратным» элементом для каждого элемента. Конфигурация автомата M есть тройка К~(х, S1, у), где Si — состояние, х — цепочка в Ai и У — цепочка в Ao ¦ Примем за х еще не прочитанную часть входной ленты (т.е. цепочку вправо от читаемого символа, включая н
Формальные свойства грамматик
141
его), за у — содержимое ленты памяти, a S1 пусть будет состояние в настоящий момент. Если / есть правило вида (1), мы говорим,что конфигурация K2 следует из конфигурации K1 по правилу /, если K1=^ay, Si, zb) и К2=(у, Sj, zbx). Автомат M допускает цепочку
w, если существует последовательность конфигураций K1..........Km,
такая, что
K1=(W1S01O)1 Km=^(e,S0,e)
и для каждого Km имеется правило /, такое, что Кщ следует из Ki по /. Автомат M допускает (порождает) язык L тогда и только тогда, когда L есть множество всех цепочек, допускаемых автоматом М.
Память устройства PDS может быть представлена в терминах множества цепочек над внутренним алфавитом; при этом переход от одной внутренней конфигурации к другой будет соответствовать прибавлению и убавлению букв на правом конце цепочки, сопоставленной данной внутренней конфигурации. Таким образом, из состояния, представленного цепочкой сри, возможен переход только в состояния, представленные цепочками <р или <рсф. Поучительно сопоставить устройство PDS, которое при этой интерпретации имеет бесконечное количество возможных состояний, с ^-ограниченным автоматом. Как было показано выше, память ^-ограниченного автомата также может быть представлена в терминах множества цепочек над внутренним алфавитом (который в данном случае совпадает с входным алфавитом). Смена состояний /е-ограниченного автомата соответствует прибавлению буквы справа к цепочке, представляющей состояние, и одновременно стиранию одной буквы на левом конце цепочки. Поэтому все множество возможных состояний конечно.
Устройство PDS представляет собой специальный тип линейно-ограниченного автомата. Для него легко доступны многие задачи, недоступные для конечного автомата, несмотря на то что оно только один раз просматривает входные данные (поскольку входная лента движется только в одном направлении). Рассмотрим, например, задачу порождения языка ZZ2, состоящего из всех цепочек вида #хсх*#, где х — непустая цепочка из а и Ь, а х*— зеркальное отражение цепочки х, т.е. цепочка х, записанная в обратном порядке — справа налево (ср. с языком L2 в предыдущей главе, разд. 3, стр. 246). Очевидно, что эта задача лежит за пределами возможностей конечного автомата, так как число необходимых для работы состояний возрастает по экспоненте, когда устройство просматривает и допускает последовательно символы из первой половины цепочки. Наряду с этим рассмотрим автомат PDS M с входным алфавитом (а, Ь, с), с внутренними состояниями S01 S1 и S2 и следующими правилами, где а принимает значения в множестве {а, Ь)-.
