Лемма о разрастании КС-языков

Лемма о разрастании КС-языков

Как и для регулярных языков, лемма о разрастании для КС-языков служит для проверки принадлежности заданного языка классу КС-языков. Доказано, что всякий язык является КС-языком тогда и только тогда, когда для него выполняется лемма о разрастании КС-языков.

Лемма о разрастании КС-языков звучит так: если взять достаточно длинную цепочку символов, принадлежащую произвольному КС-языку, то в ней всегда можно выделить две подцепочки, длина которых в сумме больше нуля, таких, чтo, повторив их сколь угодно большое число раз, можно получить новую цепочку символов, принадлежащую данному языку [6, т.1].

Формально ее можно определить следующим образом: если L — это КС-язык, то $ k Î N, k > 0, что если |a| ³ k и a Î L, то a = ebdgw, где bg¹l, |bdg| £ k и ebⁱdgⁱw Î L "i > 0 (где N — это множество целых чисел).

Пользуясь леммой, докажем, что язык L = {аⁿbⁿcⁿ | n > 0} не является КС-языком.

Предположим, что этот язык все же является КС-языком. Тогда для него должна выполняться лемма о разрастании, и существует константа k, заданная в этой лемме. Возьмем цепочку a = a^kb^kc^k, |a| > k, принадлежащую этому языку. Если ее записать в виде a = ebdgw, то по условиям леммы |bdg| £ k, следовательно, цепочка bdg не может содержать вхождений всех трех символов а, b и с — каких-то символов в ней нет. Рассмотрим цепочку eb⁰dg⁰w = edw. По условиям леммы она должна принадлежать языку, но в то же время она содержит либо k символов а, либо k символов с и при этом не может содержать k вхождений каждого из символов a, b и с, так как |edw| < 3k. Значит, какой-то символ в ней встречается меньше, чем другие — такая цепочка не может принадлежать языку L. Следовательно, язык L не удовлетворяет требованиям леммы о разрастании КС-языков и поэтому не является КС-языком.

Приведенные грамматики

Приведенные грамматики — это КС-грамматики, которые не содержат недостижимых и бесплодных символов, циклов и l-правил («пустых» правил). Приведенные грамматики называют также КС-грамматиками в каноническом виде.

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

·                   удалить все бесплодные символы;

·                   удалить все недостижимые символы;

·                   удалить l-правила;

·                   удалить цепные правила.

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

Преобразования грамматик

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

Определение: символ A Î VN называется бесплодным в грамматике G = (VT, VN, P, S), если множество { a | a Î VT^*, A Þ a} пусто.

Алгоритм удаления бесплодных символов:

Вход: КС-грамматика G = (VT, VN, P, S).

Выход: КС-грамматика G’ = (VT, VN’, P’, S), не содержащая бесплодных символов, для которой L(G) = L(G’).

Метод:

Рекурсивно строим множества N₀, N₁, ...

1.  N₀ = Æ, i = 1.

2.  N_i = {A | (A ® a) Î P и a Î (N_i-1 È VT)^*} È N_i-1.

3.  Если N_i ¹ N_i-1, то i = i+1 и переходим к шагу 2, иначе VN’ = N_i; P’ состоит из правил множества P, содержащих только символы из VN’ È VT; G’ = (VT, VN’, P’, S).

Определение: символ x Î (VT È VN) называется недостижимым в грамматике G = (VT, VN, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики.

Алгоритм удаления недостижимых символов:

Вход: КС-грамматика G = (VT, VN, P, S)

Выход: КС-грамматика G’ = (VT’, VN’, P’, S), не содержащая недостижимых символов, для которой L(G) = L(G’).

Метод:

1.  V₀ = {S}; i = 1.

2.  V_i = {x | x Î (VT È VN), (A ® axb) Î P и A Î V_i-1} È V_i-1.

3.  Если V_i ¹ V_i-1, то i = i+1 и переходим к шагу 2, иначе VN’ =

4.  V_i Ç VN;  VT’ = V_i Ç VT; P’ состоит из правил множества P, содержащих только символы из Vi; G’ = (VT’, VN’, P’, S).

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

Алгоритм приведения грамматики:

(1)обнаруживаются и удаляются все бесплодные нетерминалы.

(2)обнаруживаются и удаляются все недостижимые символы.

Удаление символов сопровождается удалением правил вывода, содержащих эти символы.

Замечание: если в этом алгоритме переставить шаги (1) и (2), то не всегда результатом будет приведенная грамматика.

Для описания синтаксиса языков программирования стараются использовать однозначные приведенные КС-грамматики.

Исключение цепных правил

Определение. Правило грамматики вида A ® B, где A,B Î VN, называется цепным.

Утверждение. Для КС-грамматики G, содержащей цепные правила , можно построить эквивалентную ей грамматику G', не содержащую цепных правил.

Идея доказательства заключается в следующем.

Если грамматика G имеет правила A ® B, B ® C, C ® aX, то такие правила могут быть заменены одним правилом А ® aX, поскольку вывод A Þ B Þ C Þ aX цепочки aX в грамматике G может быть получен в грамматике G' с помощью правила A ® aX.

В общем случае доказательство последнего утверждения можно выполнить так.

Разобьем множество правил P грамматики G на два подмножества P₁ и P₂, включая в P₁ все правила вида A ® B.

Для каждого правила из P₁ найдем множество правил S(A_i), которые строятся так:

если A_i Þ * A_j и в P₂ есть правило A_j ® a , где a - цепочка словаря (VN ÈVT)^*, то в S(A_i) включим правило A_i ® a .

Построим новое множество правил P’ путем объединения правил P₂ и всех построенных множеств S(A_i). Получим грамматику G' = {VN ,VT , P’, S}, которая эквивалентна заданной и не содержит правил вида A ® B.

В качестве примера выполним исключение цепных правил из грамматики G :

G = ({+,*,(,),a}, {E,T,F}, P={E ® E+T | T, T ®  T*F | F, F ® (E) | a}, E).

Вначале разобьем правила грамматики на два подмножества:

P₁ = {E ® T, T ® F} ,

P₂ = {E ® E+T, T ® T*F, F ®  (E) | a }

Для каждого правила из P1 построим соответствующее подмножество.

S(E) = { E ® T*F, E ® (E) | a },

S(T) = { T ® (E) | a}

В результате получаем искомое множество правил грамматики без цепных правил в виде:

P2 U S(E) U S(T) = { E ® T+T | T*F | (E) | a, T ® T*F | (E) | a, F ® (E) | a }

Преобразование неукорачивающих грамматик

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

Определение. Правило вида A ® l называется «пустым» (аннулирующим) правилом.

Определение. Грамматика называется неукорачивающей или грамматикой без «пустых» правил, если либо

1)схема грамматики не содержит аннулирующих правил,

2)либо схема грамматики содержит только одно правило вида S ® l, где S - начальный символ грамматики, и символ S не встречается в правых частях остальных правил грамматики.

Для грамматик, содержащих аннулирующие правила, справедливо следующее утверждение.

Утверждение. Для каждой КС-грамматики G', содержащей аннулирующие правила, можно построить эквивалентную ей неукорачивающую грамматику G, такую что L(G')=L(G).

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

Если же в грамматике есть правило вида S ® l, где S – начальный символ грамматики, и символ S входит в правые части других правил грамматики, то следует ввести новый начальный символ S’ и заменить правило S ® l двумя новыми правилами: S' ® l и S'® S.

В качестве иллюстрации способа построения неукорачивающих грамматик, исключим аннулирующие правила из следующей грамматики:

G ({a,b}, {S}, P = { S ® aSbS, S ® bSaS, S ® l }, S).

Выполняя все возможные замены символа S в первом правиле грамматики, получаем четыре правила вида:

S ® aSbS, S ® abS, S ® aSb, S ® ab .

Поступая аналогично со вторым правилом, имеем:

S ® bSaS, S ® baS, S ® bSa, S ® ba.

Учитывая, что начальный символ, образующий аннулирующее правило, входит в правые части других правил грамматики, заменим правило S ® l правилами вида S' ® l и S' ® S.

Построенная совокупность правил образует множество правил искомой неукорачивающей грамматики.

S' ® S | l

S ® aSbS | abS | aSb | ab | bSaS | baS | bSa | ba

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

КС-грамматики в нормальной форме

Грамматики в нормальной форме Хомского

Нормальная форма Хомского или бинарная нормальная форма (БНФ) — это одна из предопределенных форм для правил КС-грамматики. В нормальную форму Хомского можно преобразовать любую произвольную КС-грамматику. Для преобразования в нормальную форму Хомского предварительно грамматику надо преобразовать в приведенный вид.

Определение нормальной формы Хомского

КС-грамматика G(VT,VN,P,S) называется грамматикой в нормальной форме Хомского, если в ее множестве правил Р присутствуют только правила следующего вида:

1. А ® ВС, где A,B,CÎVN.

2. А ® а, где AeVN и aÎVT.

3. S ® l, если lÎL(G), причем S не должно встречаться в правых частях других правил.

Никакие другие формы правил не должны встречаться среди правил грамматики в нормальной форме Хомского [6, т. 1, 26].

КС-грамматика в нормальной форме Хомского называется также грамматикой в бинарной нормальной форме (БНФ). Название «бинарная» происходит от того, что на каждом шаге вывода в такой грамматике один нетерминальный символ может быть заменен только на два других нетерминальных символа. Поэтому в дереве вывода грамматики в нормальной форме Хомского каждая вершина либо распадается на две другие вершины (в соответствии с первым видом правил), либо содержит один последующий лист с терминальным символом (в соответствии со вторым видом правил) Третий вид правил введен для того, чтобы к нормальной форме Хомского можно было преобразовывать грамматики КС-языков, содержащих пустые цепочки символов.

Алгоритм преобразования грамматики в нормальную форму Хомского

Алгоритм позволяет преобразовать произвольную исходную КС-грамматику в эквивалентную грамматику в нормальной форме Хомского.

Условие: дана КС-грамматика G(VT,VN,P,S), необходимо построить эквивалентную ей грамматику G'(VT,VN',P',S') в нормальной форме Хомского: L(G) = L(G').

На первом шаге исходную грамматику надо преобразовать к приведенному виду. Поскольку алгоритм преобразования КС-грамматик к приведенному виду был рассмотрен выше, можно считать, что исходная грамматика уже является приведенной (не содержит бесполезных и недостижимых символов, цепных правил и l-правил).

В начале работы алгоритма преобразования приведенной КС-грамматики в нормальную форму Хомского множество нетерминальных символов VN' результирующей грамматики G' строится на основе множества нетерминальных символов VN исходной грамматики G: VN’ = VN.

Затем алгоритм преобразования работает с множеством правил Р исходной грамматики G. Он просматривает все правила из множества Р и в зависимости от вида каждого правила строит множество правил Р' результирующей грамматики G' и дополняет множество нетерминальных символов этой грамматики VN'.

1. Если встречается правило вида А®а, где AÎVN и aÎVT, то оно переносится во множество Р' без изменений.

2. Если встречается правило вида А®ВС, где A,B,CÎVN, то оно переносится во множество Р' без изменений.

3. Если встречается правило вида S®l, где S — целевой символ грамматики G, то оно переносится во множество Р' без изменений.

4. Если встречается правило вида А®аВ, где A,BÎVN и aÎVT, то во множество правил Р' включаются правила А®<АаВ>В и <АаВ>®а и новый символ <АаВ > добавляется во множество нетерминальных символов VN' грамматики G'.

5. Если встречается правило вида А®Ва, где A.BÎVN и aÎVT, то во множество правил Р' включаются правила А®В<АВа> и <АВа>®а, и новый символ <АВа> добавляется во множество нетерминальных символов VN' грамматики G'.

6. Если встречается правило вида А®аЬ, где A ÎVN и a,bÎVT, то во множество правил Р' включаются правила А®<Аа><АЬ>, <Аа>®а и <Ab>®b, новые символы <Аа> и <АЬ> добавляются во множество нетерминальных символов VN' грамматики G'.

7. Если встречается правило вида A®X₁...X_k, k>2, где AÎVN и "i: X_iÎVTÈVN, то во множество правил Р' включается цепочка правил:

А ® <X₁’><X₂...X_k>

<X₂...X_k> ® <X₂’><X₃...X_k>

<X_k-1X_k> ® <X_k-1’><X_k>

новые нетерминальные символы <Х₂...Х_k>, <Х₃...Х_k);>,..., <X_k-1,X_k> включаются во множество нетерминальных символов VN' грамматики G', кроме того, "i: если X_iÎVN, то <Х_i'>ºХ_i иначе (если X_iÎVT) <X_i'> — это новый нетерминальный символ, он добавляется во множество VN', а во множество правил Р' грамматики G' добавляется правило <Х_i'> ® X_i.

Целевым символом результирующей грамматики G' является целевой символ исходной грамматики G.

Пример преобразования грамматики в нормальную форму Хомского

Рассмотрим в качестве примера грамматику G({a,b.c}.{A,B,C,S},P,S)

Р:

S ® АаВ | Аа | be

А ® АВ | а | аС

В ® Ва | b

С ® АВ | с

Эта грамматика уже находится в приведенной форме. Построим эквивалентную ей грамматику G'(VT,VN',P',S ) в нормальной форме Хомского. Начнем построение с множества нетерминальных символов новой грамматики: VN' = {A,B,C,S}. Множество еще будет дополняться в процессе работы алгоритма.

Начнем разбирать правила этой грамматики.

Первое правило исходной грамматики S®AaB подпадает под 7-й вариант работы алгоритма. В соответствии с требованиями алгоритма заменяем его на последовательность:

S ® <A'><aB>

<aB> ® <а'><В'>

Поскольку А и В — нетерминальные символы, а «а» — терминальный символ, то получаем, что <А'>ºА и <В'>ºВ, а новое правило <а'>->а должно быть добавлено во множество правил Р' новой грамматики. Получаем последовательность правил:

S ® А <аВ>

<аВ> ® <а'>В

<а'> ® а

Во множество нетерминальных символов VN' новой грамматики необходимо добавить новые символы <аВ> и <а'>. Получаем VN' = {A,B,C,S,<aB>,<a'>}.

Второе правило исходной грамматики S ® Aa подпадает под 5-й вариант работы алгоритма. Заменяем его на два правила:

S ® A<SAa>

<SAa> ® а

Новый символ <SAa> добавляется во множество нетерминальных символов новой грамматики. Получаем VN' = {A,B,C,S,<aB>,<a'>,<SAa>}.

Третье правило исходной грамматики S ® bc подпадает под 6-й вариант работы алгоритма. Заменяем его на три правила:

S ® <Sb><Sc>

<Sb> ® b

<Sc> ® с

Новые символы <Sb> и <Sc> добавляются во множество нетерминальных символов новой грамматики. Получаем VN' = {A,B>C,S,<aB>,<a'>,<SAa>,<Sb>,<Sc>}.

Четвертое правило исходной грамматики А ® АВ подпадает под 2-й вариант работы алгоритма. Переносим его во множество правил новой грамматики без изменений.

Пятое правило исходной грамматики А ® а подпадает под 1-й вариант работы алгоритма. Переносим его во множество правил новой грамматики без изменений.

Шестое правило исходной грамматики А ® аС подпадает под 4-й вариант работы алгоритма. Заменяем его на два правила:

А ® <АаС>С

<АаС> ® а

Новый символ <АаС> добавляется во множество нетерминальных символов новой грамматики. Получаем VN' = {A,B,C,S,<aB>,<a'>,<SAa>,<Sb>,<Sc>,<AaC>}.

Седьмое правило исходной грамматики В ® Ва подпадает под 5-й вариант работы алгоритма. Заменяем его на два правила:

В ® В<ВВа>

<ВВа> ® а

Новый символ <ВВа> добавляется во множество нетерминальных символов новой грамматики. Получаем VN' = {A,B,C,S,<aB>,<a'>,<SAa>,<Sb>,<Sc>,<AaC>, <ВВа>}.

Восьмое правило исходной грамматики B ® b подпадает под 1-й вариант работы алгоритма. Переносим его во множество правил новой грамматики без изменений.

Девятое правило исходной грамматики С->АВ подпадает под 2-й вариант работы алгоритма. Переносим его во множество правил новой грамматики без изменений.

Десятое правило исходной грамматики С-»с подпадает под 1-й вариант работы алгоритма. Переносим его во множество правил новой грамматики без изменений.

Рассмотрение множества правил исходной грамматики закончено. Множество правил Р' новой грамматики G' и множество нетерминальных символов VN' этой грамматики окончательно построены. Целевым символом новой грамматики является символ S.

Получаем новую грамматику в нормальной форме Хомского, эквивалентную исходной: G'({a,b,c},{A,B,C,S,<aB>,<a'>,<SAa>,<Sb>,<Sc>,<AaC>,<BBa>}, P', S):

Р':

S ® А<аВ> | A<SAa> | <Sb><Sc>

<аВ> ® <а'>В

<а'> ® а

<SAa> ® a

<Sb> ® b

<Sc> ® с

А ® АВ | а | <АаC>C

<АаC> ® а

В ® В<ВВа> | b

<ВВа> ® а

С ® АВ | с

Видно, что при приведении грамматики к нормальной форме Хомского количество правил и нетерминальных символов в грамматике увеличивается. При этом врастет объем грамматики и несколько затрудняется ее восприятие человеком. Однако цель преобразования — не упрощение грамматики, а упрощение построения распознавателя языка на ее основе. Именно этой цели и служит нормальная форма Хомского. Далее будут рассмотрены методы построения распознавателей, в основе которых лежит именно эта форма представления грамматики КС-языка.