Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
12.1.3. Одно важное свойство НС-грамматик
В силу требования, чтобы ю никогда не было пусто, всякая НС-грамматика является полутуэвской системой специального вида, продукции которой
Pqp1 Лф?<2 -> Рф,соф2Р
удовлетворяют условию неубывания длины. Рассмотрим это условие отдельно.
12.1.4. Условие неубывания длины
Пусть имеется полутуэвская система в алфавите V=Va U Vt', пусть ее продукции
PgiQ-* P SiQ
удовлетворяют условию неубывания длины:
\gi\>\gi\-
Каждую такую продукцию (правило) можно заменить последовательностью НС-правил вида фіЛф2 —* фісофг- Делается это так. Пусть
gt = а, ... Oft
gl = Pi ---Pft • • • ?ft+<?
Введем новые (вспомогательные) символы уь •••> Yft и рассмотрим правила
Ct1Ct2Ct3 . . . Ctft-iCtft -*• Yla2al • • • Oft-lOft, Y1O2O3 .. . Ctft^ctft-»YiY203 -.. ctft_,ctft,
Y1Y2Y3 • • • Yft-iOft Y1Y2Y3 • • • Yft-iYft. Y1Y2Y3 • • • Yft-iYft-> PiY2Ys • • • Yft-iYft,
Pi ••• Pft-2Yft-iYft?i ••• Pft-2Pft-iYft. Pi • • • Pft-2?ft-iYft ?i • • • Pft-2?ft-i?ft • • • ?ft+?-
Все эти правила имеют вид
ф,лф2->фі(»ф.., I со I > 0.
В то же время ясно, что последовательное применение этих правил равносильно применению правила gi-*~gi- Можно также показать, что вместо применения этих правил в произвольном порядке их можно применять подряд и в указанном здесь порядке.
Таким образом, для всякой полутуэвской системы, продукции которой удовлетворяют условию неубывания длины, можно 196
Часть II. Некоторые замечательные классы языков
построить эквивалентную НС-грамматику. В результате можно сформулировать следующую теорему:
Теорема. Класс языков, порождаемых НС-грамматиками, совпадает с классом языков, порождаемых грамматиками, удовлетворяющими условию неубывания длины.
НС-грамматика, все правила которой удовлетворяют условию неубывания длины, называется неукорачивающей.
12.1.5. Рекурсивность языков, порождаемых неукорачивающими грамматиками
Предложение. Всякая неукорачивающая грамматика G порождает рекурсивный язык.
Доказательство. При фиксированном алфавите V данное предложение очевидно, если во всех правилах длина правой части строго больше длины левой части. Допустим, что в некоторых правилах длина правой части равна длине левой части. Множество всех цепочек длины п, порождаемых грамматикой G, имеет конечную мощность N = N (п), причем N = Af (и) < [card (V)]" ')•
Возьмем какую-нибудь цепочку из п букв и проведем все те выводы в G, начинающиеся с этой цепочки, которые не увеличивают длину. В каждом из таких выводов после (N + 1)-го шага, или даже раньше, повторно встретится какая-либо цепочка длины п, уже встречавшаяся ранее: в выводе образуется петля. Подобные петли можно выкинуть, сохраняя лишь «полезную» часть вывода. Отсюда ясно, что для любого т. в грамматике G имеется лишь конечное число таких «полезных» выводов цепочек f из аксиомы, что именно, число этих выводов не превосходит N(I)+... + N(m). Эти выводы можно перебрать и проверить, принадлежит ли f языку L(G)-, тем самым наше предложение доказано.
§ 12.2. ЛИНЕЙНО ОГРАНИЧЕННЫЕ АВТОМАТЫ
12.2.1. Определение
Линейно ограниченный автомат (сокращенно: JIO-автомат) — это система следующих объектов:
. Управляющее устройство, принимающее конечное число состояний Sj, среди которых выделено начальное состояние So и подмножество Ф заключительных состояний.
.. Лента, разбитая на ячейки, в которых пишутся (и с которых считываются) символы алфавита V, дополненного специальным граничным маркером #; этот маркер ставится в начале и в конце всякой рабочей цепочки.
') card (V) означает мощность V. Гл. XII. Грамматики непосредственно составляющих
197
... Головка, выполняющая операции трех типов: 1) запись символа на ленте, 2) считывание символа с ленты, 3) перемещение вдоль ленты влево или вправо. Эти операции выполняются в соответствии с командами вида
(аь Sі) -+(Sk, alt M),
означающими: «Если управляющее устройство находится в состоянии Sj и головка читает на ленте символ аг, то управляющее устройство переходит в состояние Sk, головка пишет на ленте вместо символа а,- символ аи и
— если M = О, остается на месте;
— если M=+1, смещается на одну ячейку вправо;
— если M = —1, смещается на одну ячейку влево». Если а{ = #, то и ai = # ').
12.2.2. Вычисления
Если на ленте ЛО-автомата написать цепочку символов из V, окаймленную маркерами ф, установить головку так, чтобы она обозревала левый маркер, и привести управляющее устройство в начальное состояние S0, то автомат начинает выполнять команды и делает это до тех пор, пока головка не дойдет до правого маркера. Если в этот момент управляющее устройство оказывается в одном из заключительных состояний, то исходная цепочка является по определению допустимой; в противном случае она не является допустимой.
Рассматриваются как детерминированные, так и недетерминированные ЛО-автоматы.
12.2.3. Языки, допускаемые JIO-автоматами
Множество всех допустимых цепочек есть по определению язык, допускаемый ЛО-автоматом.
