Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 19 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

19
4 Лабораторная работа № 4. Эквивалентные преобразования
контекстно-свободных грамматик
Цель: - закрепить понятия «эквивалентные грамматики», «приведенная
КС-грамматика»;
- сформировать умения и навыки эквивалентных преобразований
контекстно-свободных грамматик.
Основы теории
Определение 4.1. КС-грамматика называется приведенной, если она не
имеет циклов, ε-правил и бесполезных символов.
Рассмотрим основные алгоритмы приведения КС-грамматик.
Перед всеми другими исследованиями и преобразованиями КС-
грамматик выполняется проверка существования языка грамматики.
Алгоритм 4.1. Проверка существования языка грамматики
Вход: КС-грамматика ),,,( SPVVG
N
T
= .
Выход: заключение о существовании или отсутствии языка грамматики.
Определим множество нетерминалов, порождающих терминальные стро-
ки },*,|{
*
T
N
VxxZVZZN ∈⇒∈= .
Шаг 1. Положить N
0
=Ø.
Шаг 2. Вычислить
PAANN
ii
∈
→∪=
−
)(|{
1
α
и }.)(
*
1
T
i
VN ∪∈
−
α
Шаг 3. Если
1−
≠
ii
NN , то положить i=i+1 и перейти к пункту 2, иначе
считать
i
NN =
.
Если
N
S
∈ , то выдать сообщение о том, что язык грамматики существу-
ет, иначе сообщить об отсутствии языка.
Пример 4.1. Дана грамматика ),},,,{},1,0({
S
P
A
S
G
=
, где множество
правил
P
: 1)4;0)3;0)2;)1 →→→→
A
A
A
A
B
S
. Построим последова-
тельность приближений множества N:
N
0
= Ø;
N
1
= {A, B};
N
2
= {S, A, B};
N
3
= {S, A, B}.
Т.к. N
2
=N
3
, то N
= {S, A, B}, следовательно, язык грамматики существует,
потому что начальный символ
N
S
∈
.
Определение 4.2. Бесполезными символами грамматики называют:
а) нетерминалы, не порождающие терминальных строк, т.е. множество
символов
};),*(,|{
*
T
N
VxxXVXX ∈⇒¬∃∈ 
    4 Лабораторная работа № 4. Эквивалентные преобразования
контекстно-свободных грамматик

     Цель: - закрепить понятия «эквивалентные грамматики», «приведенная
КС-грамматика»;
           - сформировать умения и навыки эквивалентных преобразований
контекстно-свободных грамматик.
                                   Основы теории
     Определение 4.1. КС-грамматика называется приведенной, если она не
имеет циклов, ε-правил и бесполезных символов.
     Рассмотрим основные алгоритмы приведения КС-грамматик.
     Перед всеми другими исследованиями и преобразованиями КС-
грамматик выполняется проверка существования языка грамматики.
            Алгоритм 4.1. Проверка существования языка грамматики
      Вход: КС-грамматика G = (VT , VN , P, S ) .
      Выход: заключение о существовании или отсутствии языка грамматики.
      Определим множество нетерминалов, порождающих терминальные стро-
ки N = {Z | Z ∈ VN , Z ⇒ *x, x ∈ VT*} .
     Шаг 1. Положить N0=Ø.
      Шаг 2. Вычислить N i = N i −1 ∪ { A | ( A → α ) ∈ P и α ∈ ( N i −1 ∪ VT )*}.
      Шаг 3. Если N i ≠ N i −1 , то положить i=i+1 и перейти к пункту 2, иначе
считать N = N i .
      Если S ∈ N , то выдать сообщение о том, что язык грамматики существу-
ет, иначе сообщить об отсутствии языка.
     Пример 4.1. Дана грамматика G = ({0, 1}, {S , A, B}, P, S ) , где множество
правил P : 1) S → AB; 2) A → 0 A; 3) A → 0; 4) B → 1 . Построим последова-
тельность приближений множества N:
     N0 = Ø;
     N1 = {A, B};
     N2 = {S, A, B};
     N3 = {S, A, B}.
     Т.к. N2=N3, то N = {S, A, B}, следовательно, язык грамматики существует,
потому что начальный символ S ∈ N .
     Определение 4.2. Бесполезными символами грамматики называют:
     а) нетерминалы, не порождающие терминальных строк, т.е. множество
символов

                             { X | X ∈ VN , ¬∃( X ⇒ *x), x ∈ VT*};

                                                                               19

Страницы