Название: Информатика (формальные языки и грамматики) - Методическая разработка(С.Е. Рояк)

Жанр: Информатика

Просмотров: 1363


Занятие  9.  эквивалентные преобразования грамматик

 

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

 

Методические указания

 

Что необходимо знать:

1) теорему Огдена;

2) устранение непродуктивных, недостижимых, бесполезных символов;

3) удаление из грамматик правил вида A ® B, где A,B Î N;

4) преобразование УКС в неукорачивающую грамматику;

5) построение приведенной формы грамматики;

6) преобразование к нормальной форме Хомского любой КС-грамматики;

 

Основные определения

 

1. Для любого КС-языка L найдутся такие натуральные числа r и s, эффективно определяемые по грамматике G, порождающей язык L, что любая цепочка wÎL, длина которой больше r, может быть представлена в виде w = x1y1zy2x2, где

а) y1y2 ¹ e;

б) |y1zy2| £ s;

в) при любом n = 1,2... цепочка  принадлежит L.

Алгоритм 1. «Устранение непродуктивных символов»

Вход. КС-грамматика G=<T,N, S, P>

Выход. Эквивалентная G КС-грамматика G=<T, N,S, P>, где N – множество всех продуктивных символов.

Метод. Строим множества N0, N1, ... рекурсивно:

1. Положить N0=Æ, i=1.

2. Положить Ni={A½A®aÎP и aÎ(Ni–1UT)*} U Ni–1,i  = 1,...

3. Если Ni¹Ni–1, положить i=i+1 и перейти к шагу 2. В противном случае положить N=Ni. Положить G=<  T, N, S, P>, где P состоит из правил множества P, содержащих только символы NUT.

Алгоритм 2. «Устранение недостижимых символов»

Вход. КС-грамматика G=< T, N, S, P>

Выход. Эквивалентная G КС-грамматика G=< T, N, S, P> без недостижимых символов.

Метод Строим множества V0, V1, ... рекурсивно:

1. Положить V0={S}, i=1.

2. Положить Vi={X½ в P есть A®aXb и AÎVi–1, α,β Î( T U V)* }UVi–1, где i = 1,2,...

3. Если Vi¹Vi–1, положить i=i+1 и перейти к шагу 2. В противном случае пусть N=Vi I N, T=Vi I T, P состоит из правил множества P, содержащих только символы из Vi, G=<T, N, S,P >.

Алгоритм 3. «Устранение бесполезных символов»

Вход. КС-грамматика G=< T, N, S, P>, у которой L(G)¹Æ.

Выход. Эквивалентная G КС-грамматика G=< T, N, S, P>без бесполезных символов.

Метод

1. Применив к G алгоритм 1, получить G1=< T, N1, S, P1 >

2. Применив к G1 алгоритм 2, получить G=< T, N, S, P>.

Алгоритм 4. «Преобразование в грамматику без e-правил»

Вход. КС-грамматика G=< T,N, S, P >

Выход. Эквивалентная ей КС-грамматика G=< T, N, S, P> без e-правил.

 

Метод

1. Построить Ne={A½AÎN и } по аналогии с алгоритмами 1 и 2.

1. Построить P так:

а) если A®a0B1a1B2a2 ... Bkak принадлежит P, k³0 и BiÎNe для 1£ i £ k, но ни один символ в цепочках aj (0 £ j £ k) не принадлежит Ne, то включить P все правила вида A®a0X1a1X2a2 ... Xkak, где Xi – либо Bi, либо e, но не включать правило A®e (это могло бы произойти в случае, если все ai равны e). Добавить в множество P  правила, в которых правая часть не содержит символы из множества Ne;

b) если SÎNe, включить в P правила S®e½S, где S – новый символ SÏ N, и положить N'=NU{S}. В противном случае, положить N= N и S=S.

3. Положить G= < T,N, S, P>.

Алгоритм 5. «Устранение цепных правил»

Вход. КС-грамматика G = < T, N, S, P> без e-правил.

Выход. КС-грамматика G=< T, N, S, P> без e-правил и без цепных правил.

Метод

1. Для каждого AÎN построить NA={B½} следующим образом:

а) положить N0={A} и i=1.

b) положить Ni={C½B®ÎP и BÎNi-1, C ÎN}UNi–1,

где i = 1.2...

с) если Ni ¹ Ni–1, положить i = i+1 и повторить шаг b). В противном случае положить NA = Ni.

2. Построить P так: если B®a принадлежит P и не является цепным правилом, включить в P правило A®a для всех таких A, что BÎNA.

Алгоритм 6. «Построение приведенной формы грамматики»

Вход. КС-грамматика G=<T, N, S,P >.

Выход. Эквивалентная G приведенная КС-грамматика

G= < T, N, S, P>.

 

Метод

 

1. Применив к G алгоритм 3, получить G1=< T1,N1, S1, P1 >.

2. Применив к G1 алгоритм 4, получить G2=< T2, N2, S2, P2>.

3. Применив к G2 алгоритм 5, получить G3=< T3,N3, S3, P3 >.

4. Применив к G3 алгоритм 3, получить G'=< T', N', S ', P'>.

Алгоритм 7. «Преобразование к нормальной форме Хомского»

Вход. Приведенная КС-грамматика G=< T,N, S, P >.

Выход. КС-грамматика G=< T,N, S, P> в нормальной форме Хомского.

Метод. Грамматика G строится по G следующим образом:

1. Включить в P каждое правило из P вида A®a.

2. Включить в P каждое правило из P вида A®BC.

3. Включить в P правило S®e, если оно было в P.

4. Для каждого правила из P вида A®X1X2 ... Xk, где k>2, включить в P правила

,

 

где , если XiÎN,  – новый нетерминальный символ, если XiÎT, – новый нетерминальный символ. Символы должны быть все различны.

5. Для каждого правила из P вида A®X1X2, где хотя бы один из символов X1 и X2 принадлежит T, включить в P правило .

6. Для каждого нетерминального символа вида Xi, введенного на шагах 4) и 5), включить в P правило Xi® a, где a ÎT.  Наконец, пусть N – это N вместе со всеми новыми нетерминальными символами, введенными при построении P.

Задачи и упражнения

 

1. В грамматике G=<{a, b}, {S, A, B, C}, S, {S®AB, A®a, B®b, C®CA} > найдите и устраните непродуктивные символы.

2. В грамматике G=<{a, b, c, d, e, f, g}, S ,{S, A, B, Q}, P > найдите и устраните недостижимые символы, если:

P={S®aAcg3aBd, A®aAc½d, B®aBd½c, Q®aBc½daf},

P={S®aAb½cBd, A®aA½Ab½gg, B®cBd½ff, Q®cAb½gf}.

3. Найдите продуктивные символы в грамматике

G = <{a,b,c},{S,A,D,F,B},S,{S→ ASa |bD |F, A→ aA| cAS| DaF, B→ aA | e, D→ aA |cB, F → aA | cF | Fa}>

4. В грамматике G=< T,N, S, P> найдите и устраните бесполезные символы, если:

N={S, A, B}, T={a, b}, P={S®A½a, A®AB, B®b},

N={S, A, B, D, F, C}, T={p, d, g, f}, P={S®AB½Ap, A®g, B®DF½d, D®d, F®fF, C®p},

N={S, A, B}, T={a, b}, P={S®AB½Ap, A®aB½bS½b, B®AB½Ba, B®aS½b}.

5. Используя в качестве примера грамматики из предыдущего задания , докажите, что шаги в алгоритме удаления бесполезных символов не могут быть переставлены (т.е. нельзя вначале удалить недостижимые символы, а потом удалить непродуктивные).

6. Преобразуйте грамматику G=< T,N, S, P > в грамматику без e-правил, если:

N={S}, T={a, b}, P={S®aSbS½bSaS½e},

N={S, A, B, C}, T={a, b}, P={S®CBA, A®BB½e, B®CC½a, D®d,C®AA½b}.

7. Преобразуйте грамматику

G=<{a,(,),+,*},{S,A,B},  S, {S®S+A½A, A®A*B½B, B®(S)½a } > в грамматику без цепных правил.

8. Найдите для грамматики G=< {a, b, c},{S, A, B, C, D, E}, S,

{S®A½B, A®C½D, C®S½a½e, D®S½b, E®S½c½e} > приведенную грамматику, эквивалентную исходной грамматике, т.е.:

устраните e-правила,

устраните цепные правила,

устраните бесполезные символы.

9. Докажите, что в задании 8 пункты a), b) и c) не могут быть переставлены.

10. Для грамматики G=< T, N, S,P> постройте эквивалентную ей грамматику в нормальной форме Хомского, если

N={S}, T={a, b}, P={S®aSb½ab },

N={S, A, B}, T={a, b}, P={S®aB½bA, A®aS½bAA½a, B®bS½aBB½b}.