Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Часть /. Предварительные сведения из логики и алгебры
Пример. Пусть ЭД — латинский алфавит. Положим G = 'pa', H ='gu' К = 'по', G - W, H = Чі', К = V.
Тогда, если X = 'papagueno', то
Y = 'espalier'.
Заметим, что мы заменили на 'es' только первое вхождение 'ра\ соответствующее G, но не тронули второе вхождение 'ра\ соответствующее Р.
Шестерка (G, Н, К; Н, К) представляет собой схему продукций. Мы будем обозначать конкретную продукцию, поставленную в соответствие этой шестерке посредством слов PhQ, следующим образом:
GPHQK GPHQK. (1)
Будем говорить, что слово Y = GPHQK есть следствие слова X = = GPHQK относительно продукции (1). Продукция
GPHQK-+ GPHQK (2)
есть продукция, обратная к продукции (1).
Выражение GPHQK -> GPHQK нередко используют для обозначения схемы продукций и говорят о нем просто как о «продукции»; в таком случае PhQ должны рассматриваться как переменные, принимающие значения из некоторых множеств слов.
3.1.2. Определения
Чтобы определить комбинаторную систему, необходимо задать:
1) Конечный алфавит 91, называемый алфавитом системы. Для записи продукций может понадобиться также вспомогательный алфавит S3.
2) Выделенное непустое слово, называемое аксиомой системы.
3) Конечное число схем продукций.
Таким образом, комбинаторная система — это формальная система, в которой
. все слова над ЭД (или, быть может, над (? U S3}) являются формулами;
.. множество элементарных теорем содержит ровно одно слово — аксиому;
... правила вывода задаются продукциями. Примеры мы приведем после того, как определим некоторые частные типы комбинаторных систем. Гл. 111. Комбинаторные системы
51"
3.1.3- Продукции специальных типов _
Пусть имеется шестерка {Е, Н, E-, Е, Н, Е) (частный случай шестерки (G, Н, К\ G, Н, К) на стр. 49), где \Н\ФО. Продукции вида _
EPHQE -> EPHQE
называются полутуэвскими'); продукции, обратные к полутуэв-ским, также являются полутуэвскими.
Пустое слово можно и не писать. Тогда мы имеем
PHQ -> PHQ.
Если это не ведет к недоразумениям, мы можем сократить и эту запись:
Теперь возьмем другой частный случай нашей исходной шестерки, а именно:
(G, Е, Ei Е, Е, К),
которую можно записать, поменяв обозначения, как
(G, Е, Е; Е, Е, G). Это даст нам продукции вида
GPEQEEPEQG,
или
GPQ-> PQG,
и в конце концов (поскольку P и Q можно объединить)
GP-* PG.
Подобные продукции называются нормальными, а обратные к ним продукции _
PG-> GP
называются антинормальными-, при этом предполагается, что
IGIIGI=JfcO.
П р им е р. Пусть G = 'то', G = 'рос'; тогда нормальная схема GP PG при P = 'мат' дает
'томат' —> 'матрос'.
Антинормальная схема PG GP дает при тех же условиях
'матрос' —* 'томат',
') Термин «туэвские» используется применительно к правилам без направления, поэтому здесь понадобилась приставка «полу>. 52
Часть /. Предварительные сведения из логики и алгебры
3.1.4. Частные случаи комбинаторных систем
Пол-утуэвская система — это система, содержащая только по-лутуэвские продукции.
Туэвская система — это полутуэвская система, в которой для каждой продукции имеется обратная.
Нормальная система — это система, содержащая только нормальные продукции.
Система Поста — это система, содержащая только нормальные и антинормальные продукции, в которой для каждой продукции имеется обратная.
3.1.5. Примеры полутуэвских систем
Пример 1. Алфавит системы Я = {а, Ь), вспомогательный алфавит S = {s}, аксиома — слово V. Система содержит две по-лутуэвские продукции:
s-yab, (1)
s-*asb. (2)
Один из возможных выводов:
S -?- asb —¦> aasbb —-> aaasbbb —-> aaaabbbb.
Последнее слово (а4Ь4) записано целиком в алфавите системы; вывод не может быть продолжен.
Данный вывод слова aaaabbbb можно представить в виде сле-
Возможность такого представления вывода слова в виде дерева связана с тем, что в левых частях продукций рассматривае-
') Это представление — принципиально иное, чем описанное на стр. 54—55 (ср. примечание на стр. 55). — Прим. ред Гл. 111. Комбинаторные системы
53"
мой системы возможны только однобуквенные слова. Если, например, ввести продукцию
aabb-+ba, (3)
то вывод уже нельзя будет изобразить этим способом.
Пример 2. В этом примере мы будем использовать некоторые лингвистические термины: вместо «алфавит» мы будем говорить «словарь», вместо «слово» — «фраза» и т. п. Словарь системы
2В = {/', ип, enfant, abricot, cueille, mange}.
Вспомогательный словарь содержит следующие символы:
Ph — фраза, Gn- именная группа, Gv — глагольная группа,t Art — артикль, 5 — существительное, V — глагол.
Аксиома системы — символ Phi).
Система содержит следующие полутуэвские продукции:
Ph -* Gn Gv (1)
Gn-^ArtS (2)
Gv -+V Gn (3)
Art-* I' (4)
Art -> ип (4')
S-+enfant 'ребенок' (5)
S-+abricot 'абрикос' (5')
V-^cueille 'срывает' (6)
V -* mange 'ест' (6')
Первые три правила соответствуют в общих чертах правилам французского синтаксиса: «чтобы получить фразу, напишите именную группу, а за ней — глагольную группу», «чтобы получить именную группу, напишите артикль, а за ним — существительное» и т. д.
