Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 30 стр.

UptoLike

ВУЗ: 

ВСГУТУ | Улан-Удэ

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

Рубрика: 

4.5.1. Удаление правил вида А → В
Преобразование первого типа состоит в удалении правил А → В, или <нетерминал> →
<нетерминал>.
Покажем, что для любой КС-грамматики можно построить эквивалентную грамматику,
не содержащую правил вида: А → В, где А и В - нетерминальные символы.
Пусть имеется КС-грамматика G=(V
T
, V
N
, P, S), где множество нетерминалов V
N
={A
1
,
A
2
, . . . , A
n
}. Разобьем Р на два непересекающихся множества: P = P
1
∪ P
2
. В P
1
включены
все правила вида А
i
→ A
k
, в P
2
включены все остальные правила, т.е. P
2
= P \ P
1
. Затем для
каждого А
i
определим множество правил P(А
i
), включив в него все такие правила А
i
→ϕ, что
А
i
→* A
j
и А
j
→ ϕ, где А
j
→ ϕ ∈ P
2
. Построим эквивалентную КС-грамматику G
э
= (V
T
, V
N
,
P
э
, S), в которой множества терминальных и нетерминальных символов, а также аксиома
совпадают с теми же объектами исходной грамматики G, а множество правил P
э
получено
объединением правил множества P
2
и правил P(А
i
) для всех 1≤ i ≤n:
Пример. Пусть задана грамматика G со следующими правилами вывода S → aFb | А; А
→ аА | В; В → aSb | S; F → bc | bFc.
Построим множества правил Р2, P(S), P(A), P(B), P(F).
Определим правила для Р2: Р2 = {S → aFb; А → аА; В → aSb; F → bc | bFc}.
Определим правила для P(S): S => A => B или S =>*А; S=>В, где =>* обозначает
непосредственную выводимость. P(S) = {S → аА; S → aSb).
Определим правила для Р(А): А => В => S или А =>* В; А => S. Р(А) = {А → aSb; А →
aFb}.
Определим правила для Р(В): В => S => А или В =>* S; В =>*А. Р(В) = {В → aFb; В →
аА}.
Определим правила для P(F): так как непосредственно выводимых нетерминалов не
существует, то P(F) = 0.
Объединив полученные правила, можно записать грамматику Gэ, эквивалентную
исходной:
S → aFb | aSb | аА; А → аА | aSb | aFb;
В → аА | aSb | aFb; F → bc | bFc.
Графическая модификация метода
Аналитическое преобразование по рассмотренному алгоритму оказывается довольно
сложным. При автоматизированном преобразовании грамматик проще применить
графическую модификацию этого метода. С этой целью каждому нетерминальному символу
и каждой правой части правил из множества Р2 поставлена в соответствие вершина графа.
Из вершины с меткой U в вершину с меткой V направлено ребро, если в грамматике
существует правило U → V.
S A B F
aFb aA aSb bFc bc
PPAP
э i
i
n
=∪
=
() .
2
1
U
      4.5.1. Удаление правил вида А → В

     Преобразование первого типа состоит в удалении правил А → В, или <нетерминал> →
<нетерминал>.
     Покажем, что для любой КС-грамматики можно построить эквивалентную грамматику,
не содержащую правил вида: А → В, где А и В - нетерминальные символы.
     Пусть имеется КС-грамматика G=(VT, VN, P, S), где множество нетерминалов VN={A1,
A2, . . . , An}. Разобьем Р на два непересекающихся множества: P = P1 ∪ P2. В P1 включены
все правила вида Аi → Ak, в P2 включены все остальные правила, т.е. P2 = P \ P1. Затем для
каждого Аi определим множество правил P(Аi), включив в него все такие правила Аi→ϕ, что
Аi →* Aj и Аj → ϕ, где Аj → ϕ ∈ P2. Построим эквивалентную КС-грамматику Gэ = (VT, VN,
Pэ, S), в которой множества терминальных и нетерминальных символов, а также аксиома
совпадают с теми же объектами исходной грамматики G, а множество правил Pэ получено
объединением правил множества P2 и правил P(Аi) для всех 1≤ i ≤n:
                      n
              Pэ =   U
                     i=1
                           P ( A i ) ∪ P2 .


    Пример. Пусть задана грамматика G со следующими правилами вывода S → aFb | А; А
→ аА | В; В → aSb | S; F → bc | bFc.
    Построим множества правил Р2, P(S), P(A), P(B), P(F).
    Определим правила для Р2: Р2 = {S → aFb; А → аА; В → aSb; F → bc | bFc}.
    Определим правила для P(S): S => A => B или S =>*А; S=>В, где =>* обозначает
непосредственную выводимость. P(S) = {S → аА; S → aSb).
    Определим правила для Р(А): А => В => S или А =>* В; А => S. Р(А) = {А → aSb; А →
aFb}.
    Определим правила для Р(В): В => S => А или В =>* S; В =>*А. Р(В) = {В → aFb; В →
аА}.
    Определим правила для P(F): так как непосредственно выводимых нетерминалов не
существует, то P(F) = 0.
    Объединив полученные правила, можно записать грамматику Gэ, эквивалентную
исходной:
   S → aFb | aSb | аА;             А → аА | aSb | aFb;
   В → аА | aSb | aFb;             F → bc | bFc.

      Графическая модификация метода
    Аналитическое преобразование по рассмотренному алгоритму оказывается довольно
сложным. При автоматизированном преобразовании грамматик проще применить
графическую модификацию этого метода. С этой целью каждому нетерминальному символу
и каждой правой части правил из множества Р2 поставлена в соответствие вершина графа.
Из вершины с меткой U в вершину с меткой V направлено ребро, если в грамматике
существует правило U → V.
           aFb       aA      aSb bFc          bc




          S       A          B            F

Страницы