img197

Dodatek 4

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

W dodatku znajdują się definicje pojęć wykorzystywanych w rozdziałach lii 12. Definicje drzewowych gramatyk ekspansywnych ®_e oparte są na pracy Brainerda [29], natomiast automaty 1&df wprowadzimy tak, jak w [30], rozszerzając automat 21 of do automatu z wyjściem.

Ekspansywną gramatyką drztwową generującą drzewa <&t o nieskie-rowanych i niezaetykietowanych krawędziach, tzn. drzewa T nazywamy czwórkę

®t = (£, r, P, Z),

gdzie E = Ey U Ejv - zbiór etykiet wierzchołkowych (terminalnych i nie-terminalnych), P - zbiór produkcji o postaci:

A —* a(AiAz.. .i4_r(_a)),

gdzie A, Ai,.. -,Ar(a) G En, o G Sr, • •->4_r(_a)) jest drzewem T

(zapisanym w postaci nawiasowej) o korzeniu a i r(a) następnikach-liściach i4i, Az,..., i4_r(_a), r jest funkcją przypisującą wierzchołkowi etykietowanemu przez a liczbę jego następników, Z jest skończonym zbiorem drzew startowych.

Ekspansywną gramatyką drzewową (lub gramatyką ®edt) generującą drzewa o skierowanych i zaetykietowanych krawędziach, tzn. drzewa EDT (ang. Edge-labelled Directed Tree), nazywamy piątkę

®EDT = (E, T, r, P, Z),

gdzie E, r, Z są takie jak w poprzedniej definicji, T - zbiór etykiet krawędziowych, P - zbiór produkcji o postaci:

A —> a(TiAiT₂A2 ■ • T_r(a)i4_r(₀)),