Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
б) Возможны условные выражения, где между любыми если и то могут быть вставлены другие если ... то. Это соответствует выводам вида
(условное выражение) #(если ф0)" (условное выражение) (фі тоф2)п,
где вместо разных вхождений фо, фі и ф2 можно подставлять разные выражения2).
') О категориальных грамматиках см. Гладкий и Мельчук [1969] стр 122 — 123. Доказательство эквивалентности контекстно-свободных и категориальных грамматик см. в следующих работах: Бар-Хиллел, Гайфман и Шамир [1960], Гладкий [1966], стр. 123—132. — Прим. ред.
2) Ср. предложения на естественном языке вроде Если о том, что если он сообщит, что если завтра пойдет дождь, то он не приедет, то мы не будем его ждать, он узнает сегодня, то все будет в порядке. Здесь можно положить л = 2; тогда роль (различных вхождений) ф0 будут играть цепочки о том, что и он сообщит, что, роль фі — пустая цепочка и он узнает сегодня, роль (ps — мы не будем его ждать и все будет в порядке. — Прим. ред. Глава IX. Автомати с магазинной памятью
167
9.4.3. Фортран
Фортран записывается в нормальной форме Бэкуса, т. е. в форме КС-языка. Однако некоторые имеющиеся в Фортране ограничения с помощью нормальной формы Бэкуса выразить не удается.
9.4.4. Лисп (Дж. Маккарти)
Все S-функции, лежащие в основе системы Лисп, могут быть заданы посредством КС-грамматики. Легко убедиться в том, что предлагаемая грамматика соответствует правилам определения. Мы дадим правила порождения S-представлений, являющихся основными списочными структурами Лиспа; при этом мы не учитываем операторы Lambda, Label и Quote, которые тесно связаны с техникой программирования системы.
Предположим, что
Vr = {А, .... Z, 0, 1_____9, {,),,},
Va = [Ca (буква), Sa (атомный символ), Se (S-выражение), Pr (предикат), Ec (условное выражение), Pa (пара), Sf (S-функция), Sr (S-представление)}.
Правила соответствующей КС-грамматики будут иметь вид
V
S;] S J
\ Ee
! (CAR, Sr) (CDR, Sr) I (CONS, Sn Sr) (Pr, Sr) (Pr, Sr), Pa j
Ec (COND, Pa)
Pr-
(ATOM, Se) (EQ, Se, Se) Ec
(Se, SeU Sa J (Ca, Sa) 1
Из самой формы правил ясно, что они обеспечивают самовставление; в частности, они позволяют осуществлять рекурсивное задание списков. 158
Часть II. Некоторые замечательные классы языков
Из теорем о неразрешимости, сформулированных ранее, вытекают определенные практические следствия, уже отмечавшиеся различными авторами.
Неразрешимость проблемы эквивалентности двух грамматик означает, что не существует такой общей процедуры, которая позволяла бы для любых двух данных грамматик решить, порождают ли они одно и то же множество цепочек. Поэтому сравнивать между собой языки или семейства языков, даже таких близких, как варианты Фортрана и Алгола, оказывается нелегко: в каждом конкретном случае приходится искать свои специфические процедуры — большей частью эвристические, позволяющие получить лишь приближенные ответы. То же справедливо и для проблемы неоднозначности данного языка. Глава X
АВТОМАТНЫЕ ЯЗЫКИ И КОНЕЧНЫЕ АВТОМАТЫ
Языки, о которых пойдет речь в данной главе, были впервые введены и изучены С. К. Клини в связи с исследованием одной простой модели нейрона; эти языки мы будем называть языками Клини, или автоматными языками') (другие названия: регулярные языки, языки с конечным числом состояний2)). В последнее время А-языки нашли широкое применение в исследовании электронных схем, где был получен ряд интересных результатов, относящихся к этим языкам. Совсем в другой связи А-языки были фактически введены в рассмотрение еще А. А. Марковым3), который обратил внимание и на их значение для описания естественных языков. Наконец, сравнительно недавно А-языками занялся К. Шеннон. Исходя из тех же вероятностных соображений, что и А. А. Марков, Шеннон исследовал ряд приложений А-языков к изучению естественных языков и пришел к определению некоторого специального класса автоматов, а именно конечных автоматов4).
§ 10.1. А-ГРАММАТИКИ
Здесь мы будем рассматривать, полностью абстрагируясь от вероятностных подходов, только те общие свойства А-языков, которые связаны исключительно с «логическими» представлениями. Мы дадим ряд определений (или, скорее, вариантов определения) А-языков, а затем докажем их эквивалентность.
Хотя А-языки являются частным случаем КС-языков, представляется более интересным и полезным с методической точки зрения установить свойства А-языков независимо.
') См. выше, стр. 126, в особенности примечание.—Прим. перев.
2) Термин «языки с конечным числом состояний» (калька с англ. finite-state languages) представляется в качестве русского термина неудачным: языки, понимаемые здесь как множества цепочек, вообще не могут иметь состояний. В английском термине имеется в виду связь с конечным числом состояний «чего-то», а именно автомата, порождающего эти языки —Прим. перев.
8) Имеется в виду, очевидно, введенное А. А. Марковым (1856—1922) понятие, играющее чрезвычайно важную роль в теории вероятностей и известное в настоящее время под названием «цепи Маркова» —Прим. ред.
