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

Правило А назовём лишним, если в грамматике существует вывод цепочки  из нетерминала А без участия этого правила.

Лишние правила можно исключить из множества правил грамматики.

Пример.

Исключить лишние правила из грамматики:

1. АaABa

2. AbC

3. Abba

4. BdBC

5. B

6. CBA

7. Ca

В этой грамматике правило 3. Abba лишнее, т.к. существует вывод цепочки bba из нетерминала А без участия этого правила:

A  bC  bBa  bA  bbC  bba

1 6 5 2 7

Других лишних правил в грамматике нет. Исключая третье правило получаем грамматику без лишних правил:

1. АaABa

2. AbC

4. BdBC

5. B

6. CBA

7. Ca

Исключение -правил

Правило вида А называется -правилом. Грамматику, порождаю-щую язык, несодержащий пустую цепочку, можно преобразовать в эквивалентную ей грамматику без -правил, а грамматику, порождающую язык, содержащий пустую цепочку, можно преобразовать в эквивалентную ей грамматику с единственным -правилом S, где S – начальный нетерминал. Рассмотрим два алгоритма ислючения -правил. В первом алгоритме ис-пользуется понятие аннулирующий нетерминал – нетерминал, который может породить пустую цепочку. Для нахождения всех аннулирующих нетермина-лов грамматики можно использовать следующий алгоритм:

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

2. В полученной грамматике найти множество всех продуктивных не-терминалов. Оно так же является множеством всех аннулирующих нетер-миналов в исходной грамматике.

Алгоритм 1 исключения -правил.

1. Найти множество всех аннулирующих нетерминалов.

2. Заменить каждое из правил, правые части которых содержат хотя бы по одному аннулирующему нетерминалу, множеством новых правил. Если правая часть правила содержит k вхождений аннулирующих нетерминалов, то множество, заменяющее это правило, состоит из 2^k правил, соответствующим всем возможным способам удаления некоторых (или всех) из этих вхождений.

3. Исключить из множества правил грамматики все -правила и правила вида АА. Если в результате выполнения п.2 получены множества одинаковых правил, то из каждого такого множества оставить только одно.

4. Если исходная грамматика порождает пустую цепочку, то добавить правило S, где S – начальный нетерминал.

Пример.

Грамматика:

1. SAaB 6. Ab

2. SaB 7. BBa

3. ScC 8. B

4. AAB 9. CAB

5. AB 10. Cc

1. Находим множество аннулирующих нетерминалов. Исключая правила, содержащие хотя бы один терминал в правой части, получим грамматику:

4. AAB

5. AB

8. B

9. CAB

В этой грамматике все нетерминалы продуктивные, следовательно {A,B,C} – множество аннулирующих нетерминалов.

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

1_1. SAaB 4_1. AAB 7_1. BBa

1_2. SAa 4_2. AA 7_2. Ba

1_3. SaB 4_3. AB 8_1. B

1_4. Sa 4_4. A 9_1. CAB

2_1. SaB 5_1. AB 9_2. CA

2_2. Sa 5_2. A 9_3. CB

3_1. ScC 6_1. Ab 9_4. C

3_2. Sc 10_1. Cc

3. Исключаем из множества правил грамматики все -правила, правила вида АА и из повторяющихся оставляем только одно.

1_1. SAaB 4_1. AAB 9_1. CAB

1_2. SAa 4_3. AB 9_2. CA

1_3. SaB 6_1. Ab 9_3. CB

1_4. Sa 7_1. BBa 10_1. Cc

3_1. ScC 7_2. Ba

3_2. Sc

Алгоритм 2 исключения -правил.

Пока в грамматике есть -правила, выполнять п.1, 2 и 3.

1. Выбрать -правило А.

2. Заменить каждое из правил, правые части которых содержат хотя бы один нетерминал А, множеством новых правил. Если правая часть правила содержит k вхождений нетерминала А, то множество, заменяющее это правило, состоит из 2^k правил, соответствующим всем возможным способам удаления некоторых (или всех) из этих вхождений.

3. Исключить из множества правил грамматики правило А и правила вида ВВ. Если в результате выполнения п.2 получены множества одинаковых правил, то из каждого такого множества оставить только одно.

Пример.

Грамматика:

1. SAaB 6. Ab

2. SaB 7. BBa

3. ScC 8. B

4. AAB 9. CAB

5. AB 10. Cc

1. Выбираем -правило 8.В .

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

1_1. SAaB 4_1. AAB 7_1. BBa

1_2. SAa 4_2. AA 7_2. Ba

2_1. SaB 5_1. AB 8_1. B

2_2. Sa 5_2. A 9_1. CAB

3_1. ScC 6_1. Ab 9_2. CA

10_1. Cc

3. Исключаем из множества правил грамматики правило 8_1.В и правило 4_2.АА. Получаем грамматику:

1_1. SAaB 4_1. AAB 7_1. BBa

1_2. SAa 5_1. AB 7_2. Ba

2_1. SaB 5_2. A 9_1. CAB

2_2. Sa 6_1. Ab 9_2. CA

3_1. ScC 10_1. Cc

4. Выбираем -правило 5_2.А .

5. Исключаем из правой части каждого правила исходной грамматики всеми возможными способами вхождение нетерминала А, полученные правила добавляем в множество правил грамматики.

1_1_1. SAaB 4_1_1. AAB 9_1_1. CAB

1_1_2. SaB 4_1_2. AB 9_1_2. CB

1_2_1. SAa 5_1_1. AB 9_2_1. CA

1_2_2. Sa 5_2_1. A 9_2_2. C

2_1_1. SaB 6_1_1. Ab 10_1_1. Cc

2_2_1. Sa 7_1_1. BBa

3_1_1. ScC 7_2_1. Ba

6. Исключаем из множества правил грамматики правило 5_2_1.А. Из каждого множества одинаковых правил {1_1_2, 2_1_1}, {1_2_2, 2_2_1}, {4_1_2, 5_1_1} оставляем по одному.

1_1_1. SAaB 4_1_1. AAB 9_1_1. CAB

1_1_2. SaB 4_1_2. AB 9_1_2. CB

1_2_1. SAa 6_1_1. Ab 9_2_1. CA

1_2_2. Sa 7_1_1. BBa 9_2_2. C

3_1_1. ScC 7_2_1. Ba 10_1_1. Cc

7. Выбираем -правило 9_2_2.С .

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

1_1_1_1. SAaB 4_1_1_1. AAB 9_1_1_1. CAB

1_1_2_1. SaB 4_1_2_1. AB 9_1_2_1. CB

1_2_1_1. SAa 6_1_1_1. Ab 9_2_1_1. CA

1_2_2_1. Sa 7_1_1_1. BBa 9_2_2_1. C

3_1_1_1. ScC 7_2_1_1. Ba 10_1_1_1. Cc

3_1_1_2. Sc

9. Исключаем правило 9_2_2_1. С.

1_1_1_1. SAaB 4_1_1_1. AAB 9_1_1_1. CAB

1_1_2_1. SaB 4_1_2_1. AB 9_1_2_1. CB

1_2_1_1. SAa 6_1_1_1. Ab 9_2_1_1. CA

1_2_2_1. Sa 7_1_1_1. BBa 10_1_1_1. Cc

3_1_1_1. ScC 7_2_1_1. Ba

3_1_1_2. Sc

В полученной грамматике нет -правил, правил вида ВВ и оди-наковых правил.