Гладкий - Формальные грамматики и языки - 1973 (947381), страница 37
Текст из файла (страница 37)
в) Линейный язын )(Ь = ~а 'Ь 'са зЬ зс ... са ь 'Ь ь 'са еЬ«а а Ь а сЬ с ... гт ...сЬсЬ[ргрего,!..Срд+гУ...УР (3=2, 3, ...) допускается детерминированной МП-машиаой с 2й — ! поворотами и не допускается никакой детерминированной МП-машиной с меньшим числом поворотов и никакой детерминированной чисто стирающей МП-машиной.
г) Б-ОАЕВ язык Йз 0)!з 0 ... (порождаемый грамматикой Г, для которой А(Г) = 2) не допускается никакой детерминированной МП-машиной с ограниченным числом поворотов и никакой детерминированной чисто стира1ощей МП-машиной. 3.34. Показать, что в упражнении 4.25, в) можно взять в качестве Г итерационно-линейную ОБ.грамматику и в качестве М чисто стирающую МП-машипу с выходом. чисто ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О БЕСКОНТЕКСТНЫХ ГРАММАТИКАХ.
ДРУГИЕ СПОСОБЪ| ЗАДАНИЯ БЕСКОНТЕКСТНЪ|Х ЯЗЫКОВ Наряду с Б-грамматиками и МП-машинами существует ряд других способов задания Б-языков. Многие из них вызваны к жизни потребностями приложений: различным способам задания языка отвечают различные способы описания синтаксической структуры его предложений (цепочек), отражающие различные лингвистические аспекты этой структуры. Некоторые из таких способов будут рассмотрены в настоящей главе. Здесь же нам будет удобно изложить еще несколько фактов, относящихся к «основным» способам задания Б-языков— Б-грамматикам и МП-машинам.
$ 6.1. Категорнальные грамматики Рассмотрим конечное множество )Р, которое будем называть словарем категорий, а его элементы— э л е м е н т а р н ы м и к а те г о р и я м и. Введем в рассмотрение символы ~, [, [, ), не принадлежащие )Р. Из этих символов и элементов )Р будем строить выражения специального вида — категории (над )Р). Именно: 1. Всякая элементарная категория есть категория. |1.
Если Ф, Ч' — категории, то выражение [Ф[АР) (читается «Ф над Чт») и [Ф[Чг] (читается «Ф под Чг»)— также категории. !!1, Всякая категория является таковой либо в силу 1, либо в силу 11. Множество всех категорий над ([г будем называть к а те го риал ь ной с н с те м о й н ад )Р и обозначать 186 дополнительные сведения о е-ГРАммАтикАх [Гл, 3 кзтеГОРИАльные ГРАммзтики з В,п К([Р). Множество всех цепочек, составленных нз категорий над [Р', будет обозначаться К((Р')'. Пусть $, Ч вЂ” цепочки категорий. Мы будем говорить, что ~ непосредственно сокращается до т[, если либо 5 =ьФ[Ф[Ч") О, Ч=ьЧ'О, либо е =„'[Ф/Ч') Ч'О, т[=~ФО, где Ф, Ч' ее К((Р) и Г, Π— цепочки категорий.
3 а м е ч а н и я. 1. Можно рассматривать категорию [Ф'~Ч') как оператор, действующий справа на категорию Ф и превращающий ее в Ч'. Аналогично для [Ф/Ч"[ 2. Для запоминания удобно представлять себе непосредственное сокращение категорий как сокращение дробей, например при умножении «дроби» [Ф/Ч"[ на Ч" (справа) Ч' сокращается со «знаменателем». Далее будем говорить, что $ со кр а щ а ется до ть если существует такая последовательность цепочек категорий $з, $ь ., Е„иад [Р', что $о = $, $» = [1 и $з [ непосредственно сокращается до $з при каждом/ = 1, ..., п.
Теперь мы можем сформулировать определение категориальной грамматики. Категориальной грамматикой (К-грамм а т н к о й) называется упорядоченная четверка 6 = (Р", [6', Фз, /), где: 1), 2) 1' н У вЂ” конечные множества, называемые соответственно о с н о в н ы м с л о в арем и словарем категорий (их элементы называются соответственно о с н о в н ы м н с н м в о л ам и и элементарными категориями); 3) Фз— элемент [р', называемый главной категорией; 4) / — функция, ставящая в соответствие каждому основному символу конечное подмножество категорнальной системы К(ру); / называется пр и пи сывающей функцией. Пусть х = а[ ... ЛА — цепочка в )А, а[, ..., аз ~ 'Р' н $ = Ф[...ФА — цепочка категорий над У, Фь ...
..., ФА ~ К(([7). Мы будем говорить, что грамматика 6 сопоставляет цепочке х цепочку $, если для каждого [ = — 1, ..., л имеет место Ф; ~/(аз); грамматика 6 и р и и и с ы в а е т цепочке х категорию Ф, если либо х = а ее У и Фен /(а), либо некоторая, цепочка категорий, сопоставленная х, сокращается до Ф. Языком, определяемым К-грамматикой 6 (обозначенне: /.(6)), называется множество тех цепо- чек в основном словаре, которым грамматика 6 приписывает главную категорию. Две К-грамматики э к в и в а л е н т н ы, если онн определяют один и тот же язык. Приведем несколько примеров К-грамматик.
При этом будем явно выписывать только приписывающую функцию, имея в виду, что Фз, Фь А, К, Т, Т[ обозначают элементарные категории, в том числе Фз — главн ю категорию. Если значение /(а) припнсывающей ную кат ф нкции [ состоит из одной категории Ч', то в Ч', т вместо фу [(а) = (Ч") пишем [(а) = Ч'. П р и м е р 1. Определим приписывающую функцню /[ на словаре (а, Ь) так: /[(а) =Ф„ /,(Ь) =[ФА\ФА). Легко видеть, что цепочка, состоящая из таких категорий, с р окращается до Фз или равна Ф, тогда и только тогда, когда она имеет вид Фз([ФЕ[Фз)) (п=О,,...).
этому соответствующая грамматика определяет язык Пример 2. Определим функцию /з на (а, Ь) так: /з(а) = (А, [А/Фз) ), [з (Ь) = [А[ФА). Ясно, что всякая цепочка категорий вида ( [А/Фа[) А( [А[Фо[) ("— =1, 2,...) сокращается до Ф,. С другой стороны, цепочка категорий, являющихся значениями /з (точнее, входящих в значения /з), длина которой равна 2и, [г = 1, 2, ..., сокращается до Фз только тогда, когда она имеет внд ( [А/Фз[)" ' А ( [А[ФА[)". (Для доказательства нужно к этому утверждению присоединить еще почка категорий, являющихся значениями или в 2п — 1, частями значений /з, длина которой равна и— и=1, 2, ..., сокращается доФзили равнаФз только тогда, когда она имеет вид ([А/Фз])" ' Фз([А[Фз[)" '; оба утверж верждения доказываются одновременной индукцией.) Таким образом, соответствующая грамматика определяет язык (а"Ь" [и = 1, 2, ...).
П р и м е р 3, Определим функцию /з на словаре 1'=.(Р„..., Ры 1, й, 'Аl, ~, (,)) так: /з(Р[)=Фз (;=' ~.', й), '/,(()=К, [,())=[Ф,)[К(Ф,[[, /,(-[)= =[Фа/Ф[1, /з(й) =/зМ)=/з(~)=[ФЛФо/Ф[[1 Пусть Р([О) — множество тех цепочек, которым такая грамматика приписывает категорию [з[. Тогда: (а) Р(Фз) совпадает с множеством всех правильно построенных КАТЕГОРИАЛЬНЫЕ ГРАММАТИКИ !88 допОлнительные сВедения О в-ГРАммАтиклх !Гл. а ! е.!! ! 89 формул (ппф) логики высказываний *); (б) г" (Ф!) = [(Л)! л есть ппф); (в) Р([Фе/Ф!]) =( Ц [) ((д) а[ "л есть ппф; а=А, ~/,:э]; (г) г" (К)=((); (д) р([ФДК)Ф,]]) =[))! (е) Г([ФЛФв/Ф!]]) =[а, ~/, = ].
Утверждения (г), (д), (е) очевидны; (а), (б), (в) доказываются одновременной индукцией по длине цепочки (проведение которой предоставляется читателю). Пример 4. Определим «терм» в словаре (а„..., аа, +,, (, ), =) следующим образом: (1) а„..., аа — термы; (В) если !„(я — термы, то (!!)+(Гя) и (!!) (Гя) — термы; (Ш) других термов нет. Выражения вида !! =1, где Гн Гя — термы, назовем «формулами».
Читателю предоставляется доказать, что множество формул определяется К-грамматикой со следующей приписывающей функцией /4.. /,(а!)=Т, /«(+)=/л( )= = [Т$)[Т)Т!] ], /а ()) = К, !«() ) =[7 )[К)Т$]], /4(=) = =[Т\[Фе/Т] ]. Полезно также найти, аналогично предыдущему примеру, множества Г"(6).
Дальнейшие «абстрактные» примеры см. в упражнении 5.1. Лингвистический пример см. [Гладкий — Мельчук 1959, стр. 127 — !3!]. Примеры 3 и 4 в какой-то степени поясняют содержательный аспект работы К-грамматик: категория, приписываемая грамматикой той или иной цепочке, отражает «синтаксическую роль» последней, причем эта роль понимается либо как принадлежность к одному из немногочисленных «основных синтаксических классов» (если приписанная категория является элементарной; так, в примере 4 основные классы — «терм», «формула», «левая скобка»), либо «операционно»н «данная цепочка есть оператор, превращающий цепочку такого-то класса в цепочку такого-то класса» (так, в примере 3 категория [Фе/Ф!] приписывается унарному оператору ] и цепочкам вида (Й)а, синтаксически также ведущим себя, как унарные операторы, а категория [Ф!' [Фе/Ф!]] — бинарным операторам ос, Л, ~).
Аналогичным образом можно поступать для естественных языков; например, непереходный глагол может ') Имеется в виду следующий вариант определения ппф: (!) рг ..., р суть ппф! (и) если л, ю — ппф к о = а, У, ~, то ! [ег] В,(Ж) а [Ю) — ппф; (НЦ других ппф яет, рассматриваться как оператор, переводящий существительное в предложение. Подробнее о лингвистическом аспекте К-грамматик см. [Гладкий — Мельчук 1959, стр. 122 — 136, 150 — 153]. Перейдем к вопросу о взаимоотношении между К- грамматиками и Б-грамматиками. В одну сторону этот вопрос решается чрезвычайно просто, Пусть 6 = = ([г, )«', Фе,/) — К-грамматика.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
