Таким образом, язык L (G) примера 2.3 - праволипейный, язык /-(GJ примера 2.4 -контекстно-свободный, а язык L (G) примера 2.5 - контекстно-зависимый. Язык, порожденный грамматикой примера 2.6,- это язык без ограничений, а язык {ww\w{a, b}* и оуе} -контекстно-зависимый.

Определенные ними четыре типа грамматик и языков часто называют иерархией Хомского.

Соглашение. Далее мы будем пользоваться сокращениями КС и КЗ для терминов „контекстно-свободный" и „контекстно-зависимый" соответственно.

Каждый праволипейный язык является КС-языком, и существуют КС-языки (например, {0"1" л > 1}), которые не являются праволинейными. КС-языки, не содержащие пустой цепочки, образуют собственный подкласс КЗ-языков. А они в свою очередь образуют собственный подкласс рекурсивных множеств, которые собственно включены в класс рекурсивно-перечислимых множеств. Последние порождаются грамматиками общего вида. Доказательства этих фактов оставляем в качестве упражнений.

Часто определяют контекстно-зависимые языки как языки, определенные нами ранее, плюс все языки вида LU{e}, где L - контекстно-зависимый язык в смысле нашего определения. В таком случае КС-языки образуют собственное подмножество КЗ-языков.

Следует подчеркнуть, что, если язык задан какой-то грамматикой, это еще не значит, что его нельзя породить менее мощной грамматикой. Например, контекстно-свободная грамматика

порождает язык {О, I}*, который, как мы уже видели, можно породить и праволинейной грамматикой.

Следует также упомянуть о том, что в последнее время были введены грамматические модели, не входящие в иерархшо Хомского. Введениещвых моделей грамматик отчасти объясняется поиосами представлял

бы весь сищаксис и/или ce1vi"aнтЙ!ку""яШков~7 Некоторые пз этйх1Щёлёи приведены в" упражнениях.

2.1.4. Распознаватели

Второй распространенный метод, обеспечивающий задание языка конечными средствами, состоит в использовании распознавателей. В сущности, распознаватель-это очень схематизированный алгоритм, определяющий некоторое множество. Распознаватель можно изобразить так, как показано на рис. 2.1.

Распознаватель состоит ИЗ Трех частей -входной ленты, управляющего устройства с конечной памятью и вспомогательной, или рабочей, памяти.

вкоднйя воловт

улравляющ.ее уатройотво с конечной памятью

Рис. 2.1. Распознаватель.

Входную ленту можно рассматривать как линейную последовательность клеток, или ячеек, причем каждая ячейка содержит точно один входной символ из некоторого конечного входного алфавита. Самую левую и самую правую ячейки могут занимать особые концевые маркеры; маркер может стоять только на правом конце ленты; маркеров может не быть совсем.

Входная головка в каждый данный момент читает, или, как иногда говорят, обозревает, одну входную ячейку. За один шаг работы распознавателя входная головка может сдвинуться на одну ячейку влево, остаться неподвижной или сдвинуться на одну ячейку вправо. Распознаватель, который никогда не передвигает свою входную головку влево, называется односторонним.

Обычно предполагается, что входная головка только читает, т. е. в ходе работы распознавателя символы на входной ленте не меняются. Но можно рассматривать и такие распознаватели, входная головка которых и читает и пишет.

Памятью распознавателя может быть любого типа хранилище информации, или данных. Мы предполагаем, что алфавит памяти конечен и хранящаяся в памяти информация построена, или образована, только из символов этого алфавита, Предпо-

лагается также, что в любой момент времени можно конечными средствами описать содержимое и структуру памяти, хотя с течением времени объем памяти может становиться сколь угодно большим. Важный пример вспомогательной памяти - магазинная память (или попросту магазин), которую можно описать абстрактно как цепочку символов памяти; например, ZZ,..Z, где Zi для всех t 1, 2, ..., п принадлежит конечному алфавиту памяти Г и Zj-„верхний" символ магазина (или, как еще говорят, находится наверху или на вершине магазина).

Поведение вспомогательной памяти для заданного класса распознавателей можно охарактеризовать с помощью двух функций: функции доступа к памяти и функции преобразования памяти. Функциядоступа к памяти - это отображение множества возможных состояний, или конфигураций, памяти в конечное множество информационных символов, которое может совпадать с алфавитом памяти.

Например, единственная информация, доступная в каждый данный момент в магазине,- верхний символ. Таким образом, функция доступа к магазинной памяти /-это такое отображение Г+ в Г, что f (Z,. . .ZJ-Zj.

Функция преобразования памяти-это отображение, описывающее изменения памяти. Она отображает состояние памяти и управляющую цепочку в состояние памяти. Если предполагается, что операция над магазинной памятью заменяет верхний символ конечной цепочкой символов памяти, то соответствующую функцию преобразования памяти можно определить как такое отображение g: Г+хГ*-sr*, что

g(Z,Z,...Z„, y,...Y,) = y,...Y,Z,...Z„

Если верхний символ магазина Z заменяется пустой цепочкой, то Zg станет верхним символом и объектом очередного доступа к памяти.

Вообще именно тип памяти определяет название распознавателя. Например, распознаватель, память которого организована как магазин, можно назвать распознавателем с магазинной памятью (обычно его называют автоматом с магазинной памятью).

Ядром распознавателя является управляющее устройство с конечной памятью, под которым можно понимать программу, управляющую поведением распознавателя. Управляющее устройство представляет собой конечное множество состояний вместе с отображением, которое описывает, как меняются состояния в соответствии с текущим входным символом (т. е. находящимся под входной головкой) и текущей информацией, извлеченной из памяти. Управляющее устройство определяет также, в каком направлении сдвинуть входную головку н какую информацию поместить в память.

Распознаватель работает, проделывая некоторую последовательность шагов, или тактов. В начале/па/ста читается текущий входной символ и с помощью функции доступа исследуется память. Текущий входной символ и информация, извлеченная из памяти, вместе с текущим состоянием управляющего устройства определяют, каким должен быть этот такт. Собственно такт состоит из следующих моментов:

(1) входная головка сдвигается на одну ячейку влево, одну ячейку вправо или сохраняется в исходном положении,

(2) в память помещается некоторая информация,

(3) изменяется состояние управляющего устройства.

Поведение распо.знавателя удобно описывать в терминах конфигураций распознавателя. Конфигурация - это как бы мгновенный снимок распознавателя, на котором изображены

(1) состояние управляющего устройства,

(2) содержимое входной ленты вместе с положением входной головки,

(3) содержимое памяти.

Управляющее устройство распознавателя может быть детерминированным или недетерминированным. Если управляющее устройство недетерминированное, то для каждой конфигурации существует конечное множество возможных следующих шагов, любой из которых распознаватель может сделать, исходя из этой конфигурации.

Управляющее устройство называется детерминированным, если для каждой конфигурации существует не более одного возможного следующего шага. Недетерминированные распознаватели- удобная математическая абстракция, но, к сожалению, их обычно трудно моделировать на практике. В следующих разделах мы дадим несколько примеров и укажем приложения недетерминированных распознавателей.

, Конфигурация называется начальной, если управляющее устройство находится в заданном начальном состоянии, входная головка обозревает самый левый символ на входной лепте и память имеет заранее установленное начальное содержимое.

Конфигурация называется заключительной, если управляющее устройство находится в одном из состояний заранее выделенного множества заключительных состояний, а входная головка обозревает правый концевой маркер или, если маркер отсутствует, сошла с правого конца входной ленты. Часто требуют, чтобы память в заключительной конфигурации тоже удовлетворяла некоторым условиям.

Говорят, что распознаватель допускает входную цепочку w, если, начиная с начальной конфигурации, в которой цепочка w

записана на входной ленте, распознаватель может проделать последовательность шагов, заканчивающуюся заключительной конфигурацией.

Следует указать, что, начиная с данной начальной конфигурации, недетерминированный распознаватель может проделать много различных последовательностей шагов. Если хотя бы одна из этих последовательностей заканчивается заключительной конфигурацией, то начальная входная цепочка будет допущена.

Язык, определяемый распознавателем, - это множество входных цепочек, которые он допускает.

Для каждого класса грамматик из иерархии Хомского существует естественный класс распознавателей, определяющий тот же класс языков. Этими распознавателями являются конечные автоматы, автоматы с магазинной памятью, линейно ограниченные автоматы и машины Тьюринга. Точнее, языки из иерархии Хомского можно охарактеризовать так:

(1) Язык L праволипейный тогда и только тогда, когда он определяется (односторонним детерминированным) конечным автоматом.

(2) Язык L контекстно-свободный тогда и только тогда, когда он определяется (односторонним недетерминированным) автоматом с магазинной памятью.

(3) Язык L контекстно-зависимый тогда и только тогда, когда он определяется (двусторонним недетерминированным) линейно ограниченным автоматом.

(4) Язык L рекурсивно перечислимый тогда и только тогда, когда он определяется машиной Тьюринга.

Точные определения этих распознавателей можно найти в упражнениях и в дальнейших разделах. Конечные автоматы и автоматы с магазинной памятью играют важную роль в теории компиляции, и в этой главе мы их подробно изучим.

УПРАЖНЕНИЯ

2.1.1. Постройте праволинейные грамматики для языков, состоящих из

(а) идентификаторов, которые могут быть произвольной длины, но должны начинаться с буквы (как в Алголе);

б) идентификаторов, которые должны содержать от одного до шести символов и начинаться с буквы /, 7, /С, L, М или N (как идентификаторы целых переменных в Фортране);

(в) вещественных констант, как в ПЛ/1 или Фортране, например 10.8, 3.14159, 2., 6.625Е-27;

(г) всех цепочек из нулей и единиц, имеющих четное число нулей и четное число единиц.

2.1.2. Постройте КС-грамматики, порождающие

а) все цепочки из нулей и единиц с одинаковым числом тех и других;

б) Ка2...а„а„...ада,.е{0, 1}, l<i<n};

в) правильно построенные формулы исчисления высказываний;

г) {OnJ \ 1Ф1 и i, 1>Ъу,

д) всевозможные последовательности правильно расставленных скобок.

*2.1.3. Опишите язык, порождаемый правилами S~bSS\a. Заметьте, что не всегда легко описать язык, порождаемый конкретной грамматикой.

*2.1.4. Постройте КЗ-грамматики, порождающие

(а) 1};

(б) {ww\w {а, &} + };

(в) {w\w{a, b, с}- и число букв а в цепочке равно числу букв Ь, равному числу букв с};

г) {a"b"a"b"\m, /г> 1}.

Указание: Представьте себе множество правил КЗ-грамматики как программу. Вы можете взять специальные нетерминальные символы в роли комбинаций „входной головки" с терминальными символами.

*2Л.5. „Истинно" контекстно-зависимая грамматика G-это грамматика (N, 2, Р, S), в которой каждое правило имеет вид аЛр-ауР, где a,P€(Nu2)*, у G (N U 2)+ и Л € N. Такое правило можно истолковать в том смысле, что Л можно заменить на у только в контексте а, р. Покажите, что каждый КЗ-язык может порождаться „истинно" контекстно-зависимой грамматикой.

**2.1.6. Какой класс языков может порождаться грамматиками, использующими только левый контекст, т. е. грамматиками, в которых каждое правило имеет вид аЛ->ар, гдea€(Nu2)*, P€(NU2)-?

2.1.7. Покажите, что каждый КС-язык может порождаться грамматикой G = (N, 2, Я, 5), в которой каждое правило имеет вид либо Л--»-а, aN*, либо A-w, w2*,

2.1.8. Покажите, что каждый КЗ-язык может порождаться грамматикой G = (N, 2, Р, S), в которой каждое правило имеет вид либо сс-р, где а, p€N",либo A-w, где Л N и оу 2"*

2.1.9. Докажите, что L(G) - {a"b"c"\nl}, где G-грамматика из примера 2.5.

*2.1Л0. Можете ли Вы описать множество КС-грамматик с помощью КС-грамматики?