Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 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