img202

202

D4. Wybrane pojęcia teorii języków drzewowych i grafowych

gdzie a 6 E, A, Bi € N,    6 F, e, € {*, A}, i = 1.....r, są operatorami

osadzenia, A jest symbolem pustym.

Numerami porządkowymi nieterminali prawej strony produkcji o postaci ekspansywnej A —* a x\B\ i^Bp . ..i _rB'^r nazywamy liczby naturalne przypisane do Bi, i — 2,..., r, w następujący sposób:

1)    Bi ma numer porządkowy 1,

2)    jeśli e,- = A, i = 2.....r, to Bi ma numer porządkowy o 1 większy

niż B,_i,

3)    jeśli e, = *, i = 2,..., r, to Bi ma numer porządkowy taki sam jak

Bi-1-

Przykładowe produkcje ekspansywnej gramatyki grafowej z przypisanymi numerami porządkowymi znajdują się na rys. 12.2.

Wywód w ekspansywnej gramatyce grafowej ®EXP = (Af, S,r, P, S) jest rekurencyjnie zdefiniowany według następujących reguł:

1.    Startujemy z grafu g składającego się z jednego wierzchołka o etykiecie S i numerze porządkowym 1.

2.    Jeśli w g istnieje wierzchołek n zaetykietowany przez A oraz produkcja o postaci zredukowanej A —<■ a € P, to zastępujemy etykietę A przez a.

3.    Jeśli w g istnieje wierzchołek n zaetykietowany przez A oraz produkcja o postaci ekspansywnej A —* a XiB\ i^B^ .. .x_rB^er^r € P, to krok wywodu zgodny z tą produkcją przebiega w następujący sposób:

a) w miejsce wierzchołka n wstawiamy poddrzewo prawej strony produkcji, tzn. wierzchołek zaetykietowany przez A jest zastępowany przez wierzchołek zaetykietowany przez a, który równocześnie dziedziczy po nim numer porządkowy;