img206

206

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

Niech H = (V, E, E, T, <j>) będzie grafem IE. Wierzchołek o indeksie 1 nazywamy wierzchołkiem pierwszego poziomu.Wierzchołek tef nazywamy wierzchołkiem poziomu n, jeśli:

1)    istnieje krawędź (to, A, o) 6 E taka, że to jest poziomu n — 1,

2)    dla każdej krawędzi (u, /?, o) € E lub (t>, a, u) € E wierzchołek u jest wierzchołkiem przynajmniej poziomu n — 1.

Niech piątka &_edNLC = (£, A, T, P, Z) będzie gramatyką grafową klasy edNLC. Gramatykę <&_cdNLC nazywamy gramatyką grafową klasy L(l), jeśli:

1) P jest skończonym zbiorem produkcji o postaci (/, D, C), gdzie

a)    / € E,

b)    D jest grafem IE o opisie charakterystycznym:

n	Y* ..	. Ym, lub Vj, gdzie V) jest opisem charakterystycznym
n	rz ■ ■	• rm 0 r;
Ei	Ez ..	. Em - Ei
II	Iz ■■	■ /m - /.

wierzchołka Yi, i = 1.....m, Y\ € A, tzn. Yi jest wierzchołkiem terminal

nym, Vi jest wierzchołkiem drugiego, poziomu,

c) C : T x {m, out} —> 2^ExExrxł^,n''^>“'} jest transfomacją osadzenia.

2)    W zbiorze P nie istnieją dwie produkcje o tej samej lewej stronie i tej samej etykiecie wierzchołka o indeksie 1.

3)    Z jest grafem IE o opisie charakterystycznym spełniającym warunek lb.

Gramatykę grafową £(1) nazywamy domkniętą gramatyką grafową klasy 1.(1), jeśli dla każdego wywodu w tej gramatyce Z = ga gi —*■■■ —> g_n, graf ji, i — 0,.... n jest grafem IE.

Niech Z = go —► g\    g_n będzie wywodem w domkniętej gra

matyce grafowej L(l). Wywód nazywamy regularnym wywodem lewostronnym, jeśli:

1)    dla każdego i = 0.....n — 1, w grafie g, stosujemy produkcję dla

wierzchołka mającego najmniejszy indeks,

2)    indeksy wierzchołków nie zmieniają się w trakcie analizy.