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

UptoLike

ВУЗ: 

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

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

Рубрика: 

20
б) недостижимые нетерминалы, порождающие терминальные строки, т.е.
множество символов
};;,);*(),*(,|{
**
T
N
VxVxXXSVXX ∈∈⇒∃⇒¬∃∈
βαβα
в) недостижимые терминалы, т.е. множество символов
}.,);*(,|{
*
VXSVXX
T
∈⇒¬∃∈
βαβα
Алгоритм 4.2. Устранение нетерминалов, не порождающих терминальных
строк
Вход: КС-грамматика ),,,( SPVVG
N
T
= .
Выход: КС-грамматика
),,,( SPVVG
N
T
′
′
=
′
, такая, что
)()( GLGL =
′
и для
всех
N
VZ
′
∈ существуют выводы
x
Z
*⇒ , где
*
T
Vx ∈ .
Шаг 1. Определить множество нетерминалов, порождающих терминаль-
ные строки, с помощью алгоритма 4.1.
Шаг 2. Вычислить
Б
N
N
Б
N
N
PPPVVNNVV −
=
′
′
−
=
∩
=
′
,,, где PP
Б
⊆ -
это множество правил, содержащих бесполезные нетерминалы
NX ∈ .
Пример 4.2. Дана грамматика ),},,,,{},,,({
S
P
C
B
A
S
cba
G
=
с правила-
ми :
P
.)5;)4;)3;)2;)1 cb
C
b
B
A
B
A
AC
S
ab
S
→→→→→
Преобразуем ее в эквивалентную грамматику G
′
по алгоритму 4.2:
N
0
= Ø;
N
1
= {S, B, C};
N
2
= {S, B, C}.
Т.к.
N
1
= N
2
, то N = {S, B, C}. После удаления бесполезных нетерминалов
и правил вывода, получим грамматику
),},,,{},,,({ SPCBScbaG
′
=
′
с прави-
лами
:
P
′
.)5;)2;)1 cb
C
b
B
ab
S
→→→
Алгоритм 4.3. Устранение недостижимых символов
Вход: КС-грамматика ),,,( SPVVG
N
T
= .
Выход: КС-грамматика ),,,( SPVVG
N
T
′
′
′
=
′
, такая, что )()( GLGL =
′
и для
всех
VZ
′
∈ существует вывод
β
α
Z
S
*⇒ , где
*
)(, V
′
∈
βα
.
Определим множество достижимых символов Z грамматики G, т.е. мно-
жество
}.,);*(,|{
*
VZSVZZW ∈⇒∃∈=
βαβα
Шаг 1. Положить .
0
SW =
Шаг 2. Вычислить очередное приближение следующим образом: 
    б) недостижимые нетерминалы, порождающие терминальные строки, т.е.
множество символов

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

      в) недостижимые терминалы, т.е. множество символов

                         { X | X ∈ VT , ¬∃( S ⇒ *αXβ ); α , β ∈ V *}.

Алгоритм 4.2. Устранение нетерминалов, не порождающих терминальных
                                строк

      Вход: КС-грамматика G = (VT , V N , P, S ) .
      Выход: КС-грамматика G ′ = (VT , VN′ , P′, S ) , такая, что L(G ′) = L(G ) и для
всех Z ∈VN′ существуют выводы Z ⇒ *x , где x ∈VT* .

      Шаг 1. Определить множество нетерминалов, порождающих терминаль-
ные строки, с помощью алгоритма 4.1.
      Шаг 2. Вычислить V N′ =V N ∩ N , N Б = V N − V N′ , P ′ = P − PБ , где PБ ⊆ P -
это множество правил, содержащих бесполезные нетерминалы X ∈ N Б .
      Пример 4.2. Дана грамматика G = ({a, b, c}, {S , A, B, C}, P, S ) с правила-
ми P : 1) S → ab; 2) S → AC ; 3) A → AB; 4) B → b; 5) C → cb.
      Преобразуем ее в эквивалентную грамматику G ′ по алгоритму 4.2:
      N0 = Ø;
      N1 = {S, B, C};
      N2 = {S, B, C}.
      Т.к. N1 = N2, то N = {S, B, C}. После удаления бесполезных нетерминалов
и правил вывода, получим грамматику G′ = ({a, b, c}, {S , B, C}, P′, S ) с прави-
лами P′ : 1) S → ab; 2) B → b; 5) C → cb.

             Алгоритм 4.3. Устранение недостижимых символов
      Вход: КС-грамматика G = (VT , VN , P, S ) .
      Выход: КС-грамматика G ′ = (VT′ , V N′ , P′, S ) , такая, что L(G ′) = L(G ) и для
всех Z ∈V ′ существует вывод S ⇒ *αZβ , где α , β ∈ (V ′)* .

     Определим множество достижимых символов Z грамматики G, т.е. мно-
жество

                         W = {Z | Z ∈ V , ∃ ( S ⇒ *αZβ ); α , β ∈ V *}.

      Шаг 1. Положить W0 = S .
      Шаг 2. Вычислить очередное приближение следующим образом:


20

Страницы