3.1.2 Свойства КС-языков
Основное свойство КС-языков: Класс КС-языков замкнут относительно операции подстановки. Это означает, что, если в каждую цепочку символов КС-языка вместо некоторого символа подставить цепочку символов из другого КС-языка, то полученная цепочка также будет принадлежать КС-языку.
Класс КС-языков замкнут относительно операций объединения, конкатенации, итерации, изменения имен символов.
Замечание:
Класс КС-языков не замкнут относительно операции пересечения и операции дополнения.
Пример:
Пусть есть два языка L1={anbnci½n>0, i>0} и L2={aibncn½n>0, i>0}. Оба эти языка являются КС, но, если взять их пересечение, то получим язык L=L1ÇL2={anbncn½n>0}, который уже не является КС-языком.
Для КС-языков разрешимы проблемы пустоты языка и принадлежности заданной цепочки языку – для их решения достаточно построить МПА, распознающий данный язык. Но проблема эквивалентности двух произвольных грамматик является неразрешимой. Неразрешима и более узкая проблема – эквивалентности заданной произвольной КС-грамматики и произвольной регулярной грамматики. Тем не менее, для некоторых КС-грамматик можно построить эквивалентную им однозначную грамматику.
Детерминированные КС-языки представляют собой более узкий класс в семействе КС-языков. Этот класс не замкнут относительно операций объединения и пересечения, хотя, в отличие от всех КС-языков в целом, замкнут относительно операции дополнения.
Для класса детерминированных КС-языков разрешима проблема однозначности. Доказано, что, если язык может быть распознан с помощью ДМПА, он может быть описан с помощью однозначной КС-грамматики. Поэтому данный класс используется для построения синтаксических конструкций языков программирования.
Как и в случае с регулярными языками, для проверки того факта, что некоторый язык не принадлежит классу КС-языков, служит лемма о разрастании КС-языков. Она выполняется для любого КС-языка. Если лемма не выполняется, то это означает, что язык не относится к типу контекстно-свободных.
Лемма о разрастании КС-языков:
Если взять достаточно длинную цепочку символов, принадлежащую произвольному КС-языку, то в ней всегда можно выделить две подцепочки, длина которых в сумме больше нуля, таких, что, повторив их сколь угодно большое число раз, можно получить новую цепочку символов, принадлежащую данному языку.
Формальная запись: Если L – это КС-язык, то $ k>0, kÎN ½если ½a½³ k и aÎL, то a=bdgjm, где dj¹l, ½dgj½£ k и bdigj imÎL " i ³0.
Пример:
Проверим, является ли язык L={anbncn½n>0} КС-языком. Пусть это так, тогда для него должна выполняться лемма о разрастании КС-языков. Значит, существует некоторая константа k, о которой идет речь в этой лемме. Возьмем цепочку этого языка a=akbkck, ½a½> k. Если её записать в виде a=bdgjm, то по условиям леммы ½dgj½£ k , следовательно, цепочка dgj не может содержать вхождения всех трех символов ‘a’, ‘b’, ‘c’, т.е. в ней нет или ‘a’, или ‘c’. Рассмотрим цепочку bd0gj0m=bgm. По условиям леммы, она должна принадлежать языку L, но она содержит либо k символов ‘a’, либо k символов ‘c’. Но ½bgm½< 3k, следовательно, какие-то из символов языка входят в цепочку меньшее число раз, чем другие. Такая цепочка не может принадлежать заданному языку. Следовательно, язык L не является КС-языком.
3.1.3 Контрольные вопросы
1. Чем отличается автомат с магазинной памятью от конечного автомата и что у них общего?
2. В чём особенность такта работы МПА в случае, когда не принимается во внимание входной символ?
3. Чем отличается конфигурация МПА от конфигурации КА?
4. Может ли МПА работать при пустом стеке? А при пустой входной цепочке?
5. Что такое расширенный МПА?
6. Какие МПА являются эквивалентными?
7. К каким способам задания языка относится МПА?
8. Языки какого типа задают автоматы с магазинной памятью?
9. Какие действия со стеком может выполнять МПА на одном такте работы?
10. Построить ДМП-автоматы с опустошением стека, допускающие следующие языки: а) {0 k 1 n ½ k ³ n > 0}; б) {0 k 1 n ½ 0 < k £ n}; в) {w½wÎ{a, b}* и количество символов ’а’ и ’b’ одинаково}; г) {0 n 1 n 0 k 1 k}; д) {w½wÎ{a, b}* и количество символов ’а’ и ’b’ четно}.
11. Как можно установить, относится ли язык к контекстно-свободному типу?
12. В чём отличие леммы о разрастании КС-языков от соответствующей леммы для регулярных языков?
3.2 Преобразование КС-грамматик
3.2.1 Цели преобразований грамматик
В общем случае для КС-грамматик невозможно проверить их однозначность и эквивалентность. Но для конкретных случаев бывает можно и нужно привести заданную грамматику к некоторому определённому виду таким образом, чтобы получить грамматику, эквивалентную исходной. Заранее определённый вид зачастую позволяет упростить работу с языком и построение распознавателей для него. Итак, преобразования грамматик могут преследовать две цели:
1) упрощение правил грамматики;
2) облегчение создания распознавателя языка.
Не всегда эти цели удается совместить, тогда необходимо исходить из того, что является главным в конкретной задаче. В теории языков программирования основой является создание компилятора для языка, поэтому главной становится вторая цель. Следовательно, можно пренебречь упрощением правил (и даже смириться с некоторым их усложнением), если при этом удастся упростить построение распознавателя языка.
Все преобразования грамматик условно разбиваются на две группы:
1. исключение из грамматики тех правил и символов, без которых она может существовать (позволяет упростить правила);
2. изменение вида и состава правил грамматики. При этом могут появиться новые правила и нетерминальные символы (упрощений правил нет).
3.2.2 Приведённые грамматики
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.