img207

207

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

Niech 'SdNLC = (E, A, T, tp,Z) będzie domkniętą gramatyką grafową L(l). Potencjalnym kontekstem poprzedzającym etykiety wierzchołkowej a € £ nazywamy parę (6,x), b € A, x € I\ jeśli istnieje graf IE g = (V, E, £, T, <t>) należący do dowolnego ciągu regularnego wywodu lewostronnego w gramatyce ®_edNLC taki, że

o₍) 6 E,

gdzie k oraz / są indeksami wierzchołków b_t oraz at (odpowiednio).

Domkniętą gramatykę grafową L( 1) nazywamy gramatyką grafową klasy ETL( 1), jeśli dla każdej produkcji

(/)żl ->Xi X₂ ... X_m r, r₂ ... r_m

Ei E₂ ... E_m h h ... Im

zachodzi następujący warunek: jeśli (ł>i,y), • ■ •, (bt, y) są potencjalnymi kontekstami poprzedzającymi dla A, to istnieje element transformacji osadzenia produkcji (/) o postaci:

C(y,in) = {(Xi,b_uzi,in),...,(Xi,b_k,z_t,in)), gdzie i 6    m} oraz jeśli i = 1, to ti = y, I 6 {1, • ■ •, £}■