Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
*) В этой и предыдущей фразах слово «язык» употреблено в разных значениях (см. введение, стр. 14—15).
**) Для более точного моделирования перехода от смысла к тексту более адекватны как раз такие грамматики, в которых промежуточные объекты имеют более сложную природу, например являются деревьями (см. [Гладкий—Мельчук 1971]). Однако теория таких грамматик еще недостаточно разработана; во всяком случае,— это для нас здесь наиболее важно — теория «древесных» грамматик не может не опираться существенным образом на теорию проще устроенных «цепочечных» грамматик, которые и являются предметом настоящей книги.
***) Разумеется, это утверждение не носит характера математической теоремы. Его статус будет разъяснен в конце § 1.4.
ГРАММАТИКИ '
27
преимуществом, что по крайней мере для наиболее важных частных случаев позволяет сопоставлять порождаемым предложениям весьма естественные описания их структуры (см. ниже, § 3.1). Еще одно весьма важное достоинство данного способа состоит в том, что он хорошо вписывается в некоторую более общую систему понятий математической логики, теории алгоритмов и теории автоматов*).
Итак, мы переходим к определению порождающих грамматик в смысле Н. Хомского; до тех пор, пока не будут введены в рассмотрение другие типы грамматик, — а по большей части и после этого (когда невозможно недоразумение) — мы будем в качестве синонима для выражения «порождающая грамматика» употреблять просто слово «грамматика».
(Порождающая) грамматика — это упорядоченная четверка Г = (V, W, /, R), где: 1) V и 2) W—непересекающиеся. непустые конечные множества; 3) / — некоторый элемент W-, 4) R— конечное множество цепочек вида ф —*• ip, где ф и ^ — различные цепочки в словаре V U W и —? — символ, не входящий в V U W. Множества V и W называются соответственно основным и вспомогательным словарями (алфавитами) грамматики Г, а их элементы — соответственно основными и вспомогательными символами Г**); / называется начальным сим-во л ом Г, R—схемой Г и элементы R — правилами Г. Цепочки ф и г|з называются соответственно левой и правой частями правила ф—Объединение V\]W мы будем иногда называть полным словарем грамматики Г.
Пусть г = ф —? -ф — правило грамматики Г и Si • Ф • ёа — вхождение ф в цепочку а = ^ф|г в словаре V (J W. В этом случае мы будем говорить, что цепочка
*) Заметим, что эта система понятий возникла еще до исследований Н. Хомского, и то обстоятельство, что его концепция сразу нашла готовую формальную базу, очень сильно способствовало успешному развитию этой концепции. Таким образом, и здесь теория опередила потребности приложений, как бывает чаще всего, вопреки распространенному среди «широкой публики» ходячему мнению. __
**) Вместо слов «основной» и «вспомогательный» нередко употребляются соответственно слова терминальный н нетерминальный.
28
ОСНОВНЫЕ понятия
[ГЛ. I
г] = получается из со применением правила г
к вхождению gi * ф * цепочки ф. Если цепочка ri получается из цепочки со применением какого-либо правила Г, будем говорить, что г| непосредственно выводима из ш в Г, и писать со(= гг) или просто соf= rj.
Последовательность цепочек D = (мо, toi......юп)
(я ^ 1) называется выводом ш„ из йо в грамматике Г, если для каждого i, 1 ^ i ^ п, имеет место Шг—i {= tof. Число п называется длиной вывода D. Если существует вывод г] из w в Г, то мы будем говорить, что г| выводима из и в Г, и писать о |—гг] или СО I— Г].
Вывод (ио, (Oi, ..., (On) называется полным, если йо = / и (On — цепочка в словаре V.
Если D = (ш0, (Oi, • • ?, (On) — вывод в грамматике Г и для некоторого г'= 1, ..., п цепочка (ог получается из (Oi-1 применением правила ф —? к вхождению |г*Ф*г]г цепочки ф в (Ог-i, то мы будем, говорить, что это правило применяется на t-м шаге вывода D к вхождению |г-*Ф*г|г и что данное вхождение ф в о заменяется на г'-м шаге вывода D. Размеченным выводом, соответствующим выводу D, мы будем называть последовательность^, о', ..., (о'_,, <вп), где о' (г = 0, п— 1) — вхождение, заменяемое на i-м шаге вывода D. Одному выводу может, вообще говоря, соответствовать много размеченных выводов (см. упражнение 1.9).
Множество цепочек в основном словаре грамматики Г, выводимых из ее начального символа (иначе — множество последних цепочек всевозможных полных выводов в Г), называется языком, порождаемым грамматикой Г, и обозначается L(Г).
Из сформулированных определений видно, что существенным свойством процесса работы порождающей грамматики является его недетерминированность: если оборвать вывод на каком-либо шаге, то продолжение, вообще говоря, не восстанавливается однозначно по оставшейся части и может быть выполнено разными способами. Таким образом, грамматика — это исчисление, т. е. разрешение производить некоторые операции [Марков 1954, стр. 203] — в данном случае подстановки
ГРАММАТИКИ
29
в цепочки одних подцепочек вместо других (а не алгоритм, т. е. не предписание производить какие-то операции).
Пример. Пусть Г= ({а, Ь, с}, {А, В, С, D}, А, {А-+ВСА, ВСВ —*> D, ВС —*? be, DC -* а, сА -*? с, аА-^а}). Пример полного вывода в Г: (А, ВСА,
