Некоторые проблемы теории формальных языков.

 

Теория формальных языков быстро прогрессировала с тех пор, как Хомский впервые описал формальный язык. Однако большинство из опубликованных работ не имеет непосредственного отношения к интересующей нас проблеме разбора предложений языка программирования; эти работы скорее касаются вопросов математической теории языков и грамматик. В них определяются различные классы языков с теми или иными свойствами. Языки характеризуются в терминах грамматик, которые порождают языки лишь из некоторого определенного класса, и в терминах автоматов (машин), которые распознают языки лишь из определенного класса. Вот несколько типичных вопросов, которые рассматриваются в таких работах: если L1 и L2 - два языка из класса Т, то является ли объединение (пересечение) двух языков также языком из класса Т? Однозначна ли грамматика? Существует ли алгоритм, определяющий однозначность любой грамматики из класса Т? Эквивалентны ли две грамматики в некотором смысле?

Были выделены четыре основные класса языков в терминах грамматик, являющихся упорядоченной четверкой (V,T,P,Z), где

1. V - алфавит;

2. TÍV -алфавит терминальных символов;

3. P - конечный набор правил подстановки;

4. Z - начальный символ, принадлежащий множеству V - T.

Язык, порождаемый грамматикой, - это множество терминальных цепочек, которые можно вывести из Z. Различие четырех типов грамматик заключается в форме правил подстановки, допустимых в P. Говорят, что G - это (по Хомскому) грамматика типа 0 или грамматика с фразовой структурой, если правила имеют вид

u::=v, где uÎV и vÎV^*.

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

хUу::=хuу, где UÎV - T, uÎV⁺ и х,уÎV^*.

Термин "контекстно-чувствительная" отражает тот факт, что можно заменить U на u лишь в контексте х...у. Дальнейшее ограничение дает класс грамматик, полностью подобный классу, который мы используем; грамматика называется контекстно-свободной, если все ее правила имеют вид

U::=u, где UÎV - T и uÎV^*.

Этот класс назван контекстно-свободным потому, что символ U можно заменить цепочкой u, не обращая внимания на контекст, в котором он встретился. В КС-грамматике может появиться правило вида U:= l, где l - пустая цепочка. Однако, чтобы не усложнять терминологию и доказательства, мы не допускаем таких правил в наших грамматиках. По заданной КС-грамматике G можно сконструировать l-свободную (или неукорачивающую) грамматику G1 (наш тип), такую, что L(G1)=L(G)-{ l}. Более того, если G однозначна, то G1 также однозначна, поэтому фактически мы не вносим ограничений.

Если мы ограничим правила еще раз, приведя их к виду U::=N или U::=WN, где NÎT, а U и WÎ V - T, то получим грамматику типа 3, или регулярную грамматику. Регулярные грамматики играют основную роль, как в теории языков, так и в теории автоматов. Множество цепочек, порождаемых регулярной грамматикой, "допускается" машиной, называемой автоматом с конечным числом состояний, и наоборот. Таким образом, мы имеем характеристику этого класса грамматик в терминах автомата. Регулярные языки (те, что порождаются регулярными грамматиками), кроме того, называются регулярными множествами.

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

Один из основных вопросов, который возникает при рассмотрении грамматики, - это вопрос ее однозначности. К сожалению, было доказано, что эта проблема алгоритмически неразрешима для класса КС-грамматик. Это означает, что нельзя построить эффективный алгоритм (написать программу), который для любой заданной грамматики за конечное число шагов мог бы решить, является она однозначной или нет. Оказываются алгоритмически неразрешимыми и многие другие интересные вопросы, касающиеся контекстно-свободных языков (например, совпадают ли два языка, пересекаются ли два языка). В этом случае ищут интересные подклассы языков, для которых этот вопрос алгоритмически разрешим. Большинство доказательств теорем алгоритмической неразрешимости в теории формальных языков прямо или косвенно зависит от результатов теоремы Поста.

Доказано, что проблема однозначности для произвольной КС-грамматики алгоритмически неразрешима. Следующий вопрос, который может возникнуть: всегда ли существует однозначная грамматика для произвольного контекстно-свободного языка? Ответ отрицательный. Есть языки, для которых не существует однозначной грамматики. Такие языки называются существенно-неоднозначными.

РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И КОНЕЧНЫЕ АВТОМАТЫ.

ДИАГРАММЫ СОСТОЯНИЙ.

 

Рассмотрим регулярную грамматику G[Z]:

Z::=U0|V1

U::=Z1|1

V::=Z0|0

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

L(G)= {Bⁿ|n>0}, где B={01,10}.

Чтобы облегчить распознавание предложений грамматики G, нарисуем диаграмму состояний (рис. 2.1). В этой диаграмме каждый нетерминал грамматики G представлен узлом или состоянием; кроме того, есть начальное состояние S (предполагается, что грамматика не содержит нетерминала S). Каждому правилу Q::=T в G соответствует дуга с пометкой T, направленная от начального состояния S к состоянию Q. Каждому правилу Q::=RT соответствует дуга с пометкой T, направленная от состояния R к состоянию Q.

Мы используем диаграммы состояний, чтобы распознать или разобрать цепочку x следующим образом:

1. Первым текущим состоянием считать начальное состояние S. Начать с самой левой литеры в цепочке x и повторять шаг 2 до тех пор, пока не будет достигнут правый конец x.

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

В этих действиях можно узнать восходящий разбор. На каждом шаге (кроме первого) основой является имя текущего состояния, за которым следует входной символ. Символ, к которому приводится основа, будет именем следующего состояния. В качестве примера проведем разбор предложения 101001. Каждая строка на рис.2.2,a отражает состояние разбора перед началом выполнения шага 2.

Рис.2.1. Диаграмма состояний.

Рис.2.2. Разбор и синтаксическое дерево для цепочки 101001.

a - разбор; б - синтаксическое дерево.

 

В этом примере разбор выглядит столь простым благодаря простому характеру правил. Так как нетереминалы встречаются лишь как первые символы правой части, на первом шаге первый символ предложения всегда приводится к нетерминалу. На каждом последующем шаге первые два символа UT сентенциальной формы UTt приводятся к нетерминалу V, при этом используется правило V::=UT. При выполнении этой редукции имя текущего состояния - U, а имя следующего текущего состояния - V. Так как каждая правая часть единственна, то единственным оказывается и символ, к которому она приводится. Синтаксические деревья для предложений регулярных грамматик всегда имеют вид, подобный изображенному на рис.2.2,б.

Чтобы избавиться от проверки на каждом шаге, есть ли дуга с соответствующей пометкой, можно добавить еще одно состояние, называемое F (НЕУДАЧА), и добавить все необходимые дуги от всех состояний к F. Добавляется также дуга, помеченная всеми возможными литерами и ведущая из F обратно в F. В результате диаграмма, показанная на рис.2.1,а изменится и станет такой, как на рис.2.1,б.