img206

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 n1.

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} —> 2ExExrxł,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 —*■■■ —> gngraf ji, i — 0,.... n jest grafem IE.

Niech Z = go —► g\    gn 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.


Wyszukiwarka

Podobne podstrony:
img207 207 D4. Wybrane pojęcia teorii języków drzewowych i grafowych Niech SdNLC = (E, A, T, tp,Z)
img198 198 D4. Wybrane pojęcia teorii języków drzewowych i grafowych gdzie j4,i4i,j42ł...,j4r(a) € E
img199 D4. Wybrane pojęcia teorii języków drzewowych i grafowych    199 Automatem %DF
img200 200    D4. Wybrane pojęcia teorii języków drzewowych i grafowych Konfiguracją
img201 201 D4. Wybrane pojęcia teorii języków drzewowych i grafowych 2) wierzchołek vj jest maksymal
img202 202 D4. Wybrane pojęcia teorii języków drzewowych i grafowych gdzie a 6 E, A, Bi € N,  &
img203 203 D4. Wybrane pojęcia teorii języków drzewowych i grafowych b)    numer porz
img204 204 D4. Wybrane pojęcia teorii języków drzewowych i grafowych Na przykład, krawędzie typu: „z
img205 205 D4. Wybrane pojęcia teorii języków drzewowych i grafowych 3) Zbiór krawędzi E jest przetr

więcej podobnych podstron