Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
I. Всякая элементарная категория есть категория.
II. Если Ф, Ч'- — категории, то выражение [Ф/Т] (читается «Ф над Т») и [Ф\Т] (читается «Ф под Т») — также категории. III. Всякая категория является таковой либо в силу I, либо в силу II.
Множество всех категорий над W будем называть категориальной системой над W и обозначать
186 дополнительные сведения о б-грамматиках [гл. е
К(W). Множество всех цепочек, составленных из категорий над W, будет обозначаться К(W)*.
Пусть |, г] — цепочки категорий. Мы будем говорить, что g непосредственно сокращается до т], если либо | = ?Ф[Ф\>Р]0, ^ = ^0, либо ?, = S [Ф/^Р] ^0»
г] = ?Ф0, где Ф, и ?, 0 — цепочки категорий.
Замечания. 1. Можно рассматривать категорию [Ф\Т] как оператор, действующий справа на категорию Ф и превращающий ее в ЧЛ Аналогично для [Ф/П
2. Для запоминания удобно представлять себе непосредственное сокращение категорий как сокращение дробей, например при умножении «дроби» [ФЛР] на
(справа) Ч’’ сокращается со «знаменателем».
Далее будем говорить, что g сокращается до г|, если существует такая последовательность цепочек категорий go, gi,..., gn над W, что go = g, In = г) и gi-1 непосредственно сокращается до gi при каждом i = 1, ..., п.
Теперь мы можем сформулировать определение категориальной грамматики.
Категориальной грамматикой (К-грам-м а тик ой) называется упорядоченная четверка G = (V, W,Oo,f), где: 1), 2) V и W — конечные множества, называемые соответственно основным словарем и словарем категорий (их элементы называются соответственно основными символами и элементарными категориями); 3) Ф0 — элемент W, называемый главной категорией;
4) f — функция, ставящая в соответствие каждому основному символу конечное подмножество категориальной системы К (Г); f называется приписывающей функцией.
Пусть х = ai ... ah — цепочка в V, аи ..., ан е V и g = Ф1 ... Фи — цепочка категорий над W, фь ... ..., Фй е K(W). Мы будем говорить, что грамматика G сопоставляет цепочке х цепочку g, если для каждого 1=1......k имеет место Ф^/(а,); грамматика
G приписывает цепочке х категорию Ф, если либо х = а е V и ФеДй), либо некоторая, цепочка категорий, сопоставленная х, сокращается до Ф.
Языком, определяемым К-грамматикой G (обозначение: L(G)), называется множество тех цепо-
§ 6.1]
КАТЕГОРИАЛЬНЫЕ ГРАММАТИКИ
187
чек в основном словаре, которым грамматика G приписывает главную категорию.
Две К-грамматики эквивалентны, если они определяют один и тот же язык.
Приведем несколько примеров К-грамматик. При этом будем явно выписывать только приписывающую функцию, имея в виду, что Ф0, Фь Л, К, Т, Ту обозначают элементарные категории, в том числе Фо — главную категорию. Если значение f(a) приписывающей функции f состоит из одной категории W, то вместо f(a) = {Т} пишем f{a) = Т.
Пример 1. Определим приписывающую функцию Д на словаре {а, Ь] так: !\{а) = Ф0, f\ {b) = [Ф<ДФо]. Легко видеть, что цепочка, состоящая из таких категорий, сокращается до Ф0 или равна Ф0 тогда и только тогда, когда она имеет вид Ф0([Ф<ДФо])" (п = 0, 1,...)- Поэтому соответствующая грамматика определяет язык {abn | п — О, 1, ...}.
Пример 2. Определим функцию f2 на {а, Ь} так: f2(a) = {A, [Л/Ф0]}, М&) = И\Фо]- Ясно, что всякая
цепочка категорий вида ([Л/Фо])"-1 Л([Л\Ф0])" (п =
= 1, 2, ...) сокращается до Ф0. С другой стороны, цепочка категорий, являющихся значениями f2 (точнее, входящих в значения f2), длина которой равна 2п, п — 1, 2, сокращается до Ф0 только тогда, когда она имеет вид ([Л/Фо])"-1 Л([Л\Ф0])П. (Для доказательства нужно к этому утверждению присоединить еще одно: цепочка категорий, являющихся значениями или частями значений f2, длина которой равна 2л—1, п— 1,2,..., сокращается до Ф0или равна Ф0 только тогда, когда она имеет вид ([Л/Ф0] )п~1 Ф0([Л\Ф0])Л-1; оба утверждения доказываются одновременной индукцией.) Таким образом, соответствующая грамматика определяет язык {апЬп | п = 1,2,...}.
Пример 3. Определим функцию /3 на словаре
V ={ри рк, "1, &, V, =5, (,)} так: Мр,) = Ф0
(i = l....k), f3(() = K, f3()) = [<I>oWI>i]J, Ы1) =
=[Ф0/Ф1], f3 (&)=fs сv)=f3 (=э)=[m<s>M ]?
Пусть F(0) — множество тех цепочек, которым такая грамматика приписывает категорию 0. Тогда: (а) ^(Фо) совпадает с множеством всех правильно построенных
188 ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О Б-ГРАММАТИКАХ [ГЛ. 6
формул (ппф) логики высказываний *); (б) /7(Ф1) = {(2()i 2( есть ппф}; (в) /?([®0/®i]) = {_l}U{(2()a| 21 есть ппф; а = &, V, =>}; (г) F (К) = {(}?, (д) F([<W\<!>,]]) = {)}; (е) Р([Ф1\[Ф01Ф1)})^{&, V, =>}.
Утверждения (г), (д), (е) очевидны; (а), (б), (в) доказываются одновременной индукцией по длине цепочки (проведение которой предоставляется читателю).
Пример 4. Определим «терм» в словаре {а,, ..., ак, +. *.(>)> ==} следующим образом: (i) аи ..., ак — термы;
(ii) если tu t2 — термы, то (^) + (4) и (^) • (/2) — термы;
(iii) других термов нет. Выражения вида tl=t2, где tb t2 — термы, назовем «формулами».
Читателю предоставляется доказать, что множество формул определяется К.-грамматикой со следующей приписывающей функцией f4: f4(al) = T, f4(+) = f4(.) =
