Регулярные выражения и языки (стр. 22 )

Базис. Для произвольной цепочки а терминалов и переменных считаем, что а => а.

g

Таким образом, любая цепочка порождает саму себя.

Индукция. Если а => f3 и /3 => у, то а => у. Таким образом, если а может породить

g        g        g

13 за нуль или несколько шагов, и из /3 еще за один шаг порождается у, то а может поро­дить у. Иными словами, а => /3 означает, что для некоторого п> 1 существует последо­вательность цепочек yh у2, ..., у„, удовлетворяющая следующим условиям. 1. а=у,. 2- 13=у„.

3. Для i = 1,2, ..., п-1 имеет место отношение у, => yf4.

* •

Если грамматика G подразумевается, то вместо => используется обозначение =>.

Пример 5.5. Вывод о том, что а*(а + 600) принадлежит языку переменной Ј, можно отразить в порождении этой цепочки, начиная с Е. Запишем одно из таких порождений. Ј=> Е* Ј=> /* Ј=> а* Ј=> а * (Ј) =>а*(Е + Е)=>а*(1 + Е)=>а* (а+ Е)=> а*(а + Г)=$а*(а + Ю)=$а*(а + /00) => а * (а + 600) На первом шаге Ј заменяется телом продукции 3 (см. рис. 5.2). На втором шаге приме­няется продукция 1 для изменения Ј на / и т. д. Заметим, что мы систематически придержи­вались тактики замены крайней слева переменной в цепочке. На каждом шаге, однако, мы можем произвольно выбирать переменную для замены и использовать любую из продук­ций для этой переменной. Например, на втором шаге мы могли бы изменить второе Ј на (Ј), используя продукцию 4. В этом случае Ј*Ј=>Ј* (Ј). Мы могли бы также выбрать замену, не приводящую к той же самой цепочке терминалов. Простым примером было бы использование продукции 2 на первом же шаге, в результате чего Е=> Е + Е, но теперь ни­какая замена переменных Ј не превратит цепочку Е + Ева* (а + 600).

Мы можем использовать отношение => для сокращения порождения. На основании

базиса нам известно, что Ј => Ј Несколько использований индукции дают нам утвер - * * *

ждения Ј=> Ј*Ј, Ј=> I* Е и так далее до заключительного Ј => а* (а + 600).

Две точки зрения — рекурсивный вывод и порождение — являются эквивалентными. Таким образом, можно заключить, что цепочка терминалов w принадлежит языку неко­торой переменной А тогда и только тогда, когда А => w. Доказательство этого факта, од­нако, требует некоторых усилий, и мы отложим его до раздела 5.2. □

5.1.4. Левые и правые порождения

Для ограничения числа выборов в процессе порождения цепочки полезно потребо­вать, чтобы на каждом шаге мы заменяли крайнюю слева переменную одним из тел ее продукций. Такое порождение называется левым (leftmost), и для его указания использу­ются отношения => и =>. Если используемая грамматика G не очевидна из контекста, то

lm 1т

ее имя G также добавляется внизу.

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

переменная на одно из тел. В таком случае порождение называется правым (rightmost), и

*

для его обозначения используются символы => и =>. Имя используемой грамматики

rm        гт

также при необходимости записывается внизу.

Пример 5.6. Порождение из примера 5.5 в действительности было левым, и его мож­но представить следующим образом.

Ј=>Ј*Ј=>1*Е=>а*Е=>

lm        lm        lm        1т

а * (Ј) => а *(Ј + Ј) => а* (1 + Е) => а * (а + Ј) =>

Im        Im        Im        1т

а * (а + I) => а * (а + /0) а* (а + /00) => а * (а + Ь00)

Im        1т        /т

Обозначения для порождений, заданных КС-грамматиками

Существует немало соглашений, напоминающих о роли тех или иных символов, ис­пользуемых в КС-грамматиках. Будем использовать следующие соглашения.

Строчные буквы из начала алфавита (а, Ъ и т. д.) являются терминальными симво­лами. Будем предполагать, что цифры и другие символы типа знака + или круглых скобок — также терминалы. Прописные начальные буквы (А, В и т. д.) являются переменными. Строчные буквы из конца алфавита, такие как w или z, обозначают цепочки тер­миналов. Это соглашение напоминает, что терминалы аналогичны входным сим­волам конечного автомата. Прописные буквы из конца алфавита, вроде X или У, могут обозначать как терми­налы, так и переменные. Строчные греческие буквы (а, (5 и т. д.) обозначают цепочки, состоящие из терми­налов и/или переменных.

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

Можно резюмировать левое порождение в виде Е => а * (а + 300) или записать несколь-

1т

ко его шагов в виде выражений типа Е* Е => а* (Е).

1т

Следующее правое порождение использует те же самые замены для каждой перемен­ной, хотя и в другом порядке.

Ј=> Е* Е => Е*(Е) => Ј * (Ј + Е) =>

rm        rm        гт        гт

Ј*(Ј + /) => Ј*(Ј +10) => Ј * (Ј + /00) Ј * (Ј + 600)

гт        гт        гт        гт

Ј*(/+М)0) => Е*(а + Ь00) => I*(a + b00) => а*(а + 600)

гт        гт        гт

Данное порождение также позволяет заключить, что Ј => а* (а + 600).

гт

Любое порождение имеет эквивалентные левое и правое порождения. Это означает, что если w — терминальная цепочка, а А — переменная, то А => w тогда и только тогда, когда А => w, а также А => w тогда и только тогда, когда А => w. Эти утверждения дока-

1п!        гт

зываются также в разделе 5.2.

5.1.5. Язык, задаваемый грамматикой

Если G = (V, T, P,S)— КС-грамматика, то язык, задаваемый грамматикой G, или язык грамматики G, обозначается L(G) и представляет собой множество терминальных цепочек, порождаемых из стартового символа. Таким образом,

L(G)={we f\S=>w}.

g

Если язык L задается некоторой КС-грамматикой, то он называется контекстно - свободным, или КС-языком. Например, мы утверждали, что грамматика, представленная на рис. 5.1, определяет множество палиндромов в алфавите {0, 1}. Таким образом, множество палиндромов является КС-языком. Можем доказать это утверждение следующим образом.

Теорема 5.7. Язык L(Gpal), где Gpai— грамматика из примера 5.1, является множест­вом палиндромов над {0, 1}.

Доказательство. Докажем, что цепочка w в {0, 1}* принадлежит L(Gpa,) тогда и толь­ко тогда, когда она является палиндромом, т. е. w = wR.

(Достаточность) Пусть w — палиндром. Докажем индукцией по |w|, что w е L(Gpai).

Базис. Если |w| = 0 или |w| = 1, то w представляет собой е, 0 или 1. Поскольку в грам-

♦

матике есть продукции Р —> Ј, Р —> О, Р —> 1, то во всех случаях Р => w.

Индукция. Пусть |w| > 2. Так как w = wR, она должна начинаться и заканчиваться од­ним и тем же символом, т. е. w = 0x0 или w = 1x1. Кроме того, х является палиндромом, т. е. х = xR. Заметим, что нам необходим факт w > 2, чтобы обеспечить наличие двух раз­личных нулей или единиц на обоих концах w.

*

Если w = 0x0, то по предположению индукции Р => х. Тогда существует порождение

w из Р: Р 0Р0 => 0x0 = w. Если w = 1x1, то рассуждения аналогичны, но с использова­нием продукции Р —> \Р\ на первом шаге. В обоих случаях заключаем, что we L(Gpai), тем самым завершая доказательство.

*

(Необходимость) Предположим, что we L(Gpai), т. е. Р => w. Докажем, что w— па­линдром. Проведем доказательство индукцией по числу шагов в порождении w из Р.

Базис. Если порождение имеет один шаг, то он использует одну из трех продукций, не имеющих Р в теле, т. е. порождение представляет собой Р => Ј, Р => 0 или Р => \. Так как Ј, 0 и 1 — палиндромы, то базис доказан.

Индукция. Предположим, что порождение состоит из п+ 1 шагов, где п> 1, и что утверждение индукции верно для всех порождений из п шагов. Таким образом, если

Р =ф х за п шагов, то х является палиндромом.

Рассмотрим (п + 1)-шаговое порождение, которое должно иметь вид

Р 0Л) =» 0x0 = w

или Р => lPl => lxl = w, поскольку п + 1 шаг— это как минимум два шага, и только ис­пользование продукций Р —> Of0 или Р —» 1Р1 делает возможными дополнительные ша-

*

ги порождения. Заметим, что в обоих случаях Р => х за п шагов.

По предположению индукции х является палиндромом, т. е. x=xR. Но тогда и 0x0, и 1x1 — палиндромы. Например, (0x0)R = 0xR0 = 0x0. Делаем вывод, что w— палиндром и завершаем доказательство. □

5.1.6. Выводимые цепочки

Порождения из стартового символа грамматики приводят к цепочкам, имеющим осо­бое значение. Они называются "выводимыми цепочками" ("sentential form"). Итак, если

*

G = (У, Т, Р, S) — КС-грамматика, то любая цепочка а из (FU Т), для которой S ==> а, называется выводимой цепочкой. Если S => а, то а является левовыводимой цепочкой, a

Im

если S => а, то — правовыводимой. Заметим, что язык L(G) образуют выводимые це-

тт

почки из Т*, состоящие исключительно из терминалов.

Пример 5.8. Рассмотрим грамматику выражений (см. рис. 5.2). Например, Е* (1+ Е) является выводимой цепочкой, поскольку существует следующее порождение.

Ј=>Ј*Ј=>Ј*(Ј) Ј*(Ј + Ј) =>Ј*(/ + Ј) Однако это порождение не является ни левым, ни правым, так как на последнем шаге за­меняется среднее Ј.

Примером левовыводимой цепочки может служить а * Ј со следующим левым поро­ждением.

Ј=>Ј*Ј=> /*Ј=> а*Ј

hn        Im        Im

Аналогично, порождение

rm        rm        rm

показывает, что Ј*(Ј + Ј) является правовыводимой цепочкой. □

Способ доказательства теорем о грамматиках