Date post: | 05-Apr-2015 |
Category: |
Documents |
Upload: | svenja-wunderlich |
View: | 104 times |
Download: | 1 times |
Baumautomaten
Christian Klein
Betreuer : Tim Priesnitz
SS 2003 Seminar “Logische Aspekte von XML”
Gert Smolka
Programming Systems Lab
Universität des Saarlandes
Übersicht
• Wortautomaten <-> Baumautomaten • Bottom-up und Top-down Automaten• Unranked Automaten• Tupelautomaten
Motivation• Endliche Automaten erkennen Bäume nur
pfadweise.
f
a b
nicht von DEA erkennbar => Baumautomaten
a -> qa, b -> qb
f(qa, qb) -> qfinal, f(qb, qa) -> qfinal
f(qa, qa) -> qfalsch, f(qb, qb) -> qfalsch
f
b a
Äquivalente Definition von endlichen Automaten• vorher : Δ Teilmenge von Q x Σ -> Q• jetzt : Δ Teilmenge von Q x Σ -> 2Q
p r
q
a a
Darstellung: regulärer Ausdruck auf rechter Seite : (q, a) -> p ∪ rFalls q Startzustand (q, a) -> p ∪ r ∪ ε
-> Angabe der Startzustände nicht mehr benötigt
wird zu : (q, a) -> {p, r}
Zwei Traversierungsstrategien
• klassisch : von vorne nach hinten; akzeptiere wenn am Wortende Endzustand
• weitere Strategie : von hinten nach vorne; starte mit Endzuständen und gehe Δ-Regeln rückwärts, akzeptiere wenn ε am Wortanfang
q0
q2
q1
ba
a
b
σ a b b a b aq q0 q1 q1 q2 q1 q2
ba
q2 (a)-> q1 (b)-> q0 ∪ q1 ∪ q2
(a)-> ε ∪ q0 ∪ q2 (b)-> ε ∪ q1 (b)-> q0 ∪ q1 ∪ q2 (a) -> ε ∪ q0 ∪ q2
Definition Baumautomat
Ein endlicher Baumautomat ist ein Tupel (Q, Σ, F, Δ), mit Alphabet Σ, Zustandsmenge Q, eine Teilmenge F von Q , und Übergangsrelation Δ
Die Regeln aus Δ sind von der Form(q0, σ) -> (q1
1,..., q1n) ∪ ... ∪ (qm
1,..., qmn) für
arity(σ) = n
Baumautomaten gehen zurück auf Doner (1965) und Thatcher & Wright (1965)
Lauf eines Automaten (Q, Σ, F, Δ)
• Lauf r auf Baum t ist Funktion Pos(t) -> Q, so dass für alle p aus Pos(t) gilt :
Wenn n = arity( t(p) ), r(p) = q0 , r(pi) = qi ( i = 1,...,n ),
dann (q0, t(p) ) -> (q1,...,qn) matcht Regel in Δ.
• Ein Lauf heißt erfolgreich, wenn r(ε) in F.
• Sprache L(M) = { t | t ist Σ-Baum und es gibt erfolgreichen Lauf von M auf t}
Automat und Lauf Σ = {and/2, not/1, 0/0,
1/0}Q = {q0, q1} F={q1} Δ = { (q0, 0) -> ε,
(q1,1) -> ε, (q0, not) -> q1, (q1, not) -> q0,(q0, and) -> (q0, q0)
∪ (q0, q1) ∪ (q1, q0)
(q1, and) -> (q1, q1) }
and
and not
not 1 0
0
q1
q1 q1
q1 q0 q0
q0
Bottom-up vs. Top-down
Zwei spezielle Strategien Lauf zu berechnen :
• von den Blättern zur Wurzel ( Bottom-up )
F beschreibt Endzustände
• von der Wurzel zu den Blättern ( Top-down )
F beschreibt Startzustände
Bottom-up Berechnung
Δ = { (q0, 0) -> ε, (q1,1) -> ε, (q0, not) -> q1, (q1, not) -> q0,
(q0, and) -> (q0, q0) ∪ (q0, q1) ∪ (q1, q0), (q1, and) -> (q1, q1) }
Baum: erfolgreiche Berechnung :
Σ = {and/2, not/1, 0/0, 1/0} Q = {q0, q1} F={q1}
and
not and
0 not 1
0 q0
q0 q1 q1
q1q1
q1
Alternative algebraische Charakterisierung
• Stelle Baum durch Term da
• (q0, σ) -> (p1,...,pn) ∪...∪ (q1,..., qn)
wird interpretiert durch Termersetzungsregeln
σ(p1,...,pn) -> q0
...
σ(q1,...,qn) -> q0
Lauf durch Termersetzung
and( not( and( 1, 1 ) ), and( not( 0 ), 1 ) )
Δ = { (q0, 0), (q1,1), (q0, not)-> q1, (q1, not)-> q0, (q0, and)-> (q0, q0) ∪ (q0, q1) ∪ (q1, q0), (q1, and)-> (q1, q1) }
Lauf durch Termersetzung
and( not( and( 1, 1 ) ), and( not( 0 ), 1 ) )
-> and( not( and( q1, q1 ) ), and( not( q0 ) , q1 ) )
Δ = { (q0, 0), (q1,1), (q0, not)-> q1, (q1, not)-> q0, (q0, and)-> (q0, q0) ∪ (q0, q1) ∪ (q1, q0), (q1, and)-> (q1, q1) }
Lauf durch Termersetzung
and( not( and( 1, 1 ) ), and( not( 0 ), 1 ) )
-> and( not( and( q1, q1 ) ), and( not( q0 ) , q1 ) )
-> and( not( q1 ) , and( q1, q1) )
Δ = { (q0, 0), (q1,1), (q0, not)-> q1, (q1, not)-> q0, (q0, and)-> (q0, q0) ∪ (q0, q1) ∪ (q1, q0), (q1, and)-> (q1, q1) }
Lauf durch Termersetzung
and( not( and( 1, 1 ) ), and( not( 0 ), 1 ) )
-> and( not( and( q1, q1 ) ), and( not( q0 ) , q1 ) )
-> and( not( q1 ) , and( q1, q1) )
-> and ( q0, q1)
Δ = { (q0, 0), (q1,1), (q0, not)-> q1, (q1, not)-> q0, (q0, and)-> (q0, q0) ∪ (q0, q1) ∪ (q1, q0), (q1, and)-> (q1, q1) }
Lauf durch Termersetzung
and( not( and( 1, 1 ) ), and( not( 0 ), 1 ) )
-> and( not( and( q1, q1 ) ), and( not( q0 ) , q1 ) )
-> and( not( q1 ) , and( q1, q1) )
-> and ( q0, q1)
-> q0 wird also nicht akzeptiert
Δ = { (q0, 0), (q1,1), (q0, not)-> q1, (q1, not)-> q0, (q0, and)-> (q0, q0) ∪ (q0, q1) ∪ (q1, q0), (q1, and)-> (q1, q1) }
Deterministische Bottom-up Baumautomaten
Definition: Ein Bottom-up Baumautomat heißt deterministisch, wenn es in Δ keine zwei Regeln (qo, σ) -> REGEXP1 ∪ (q1,..., qn) und (p0, σ) -> REGEXP2 ∪ (q1,..., qn) gibt.
Satz : Für jede Sprache L, die von einem nichtdeterministischen Bottom-up Automaten erkannt wird, gibt es einen deterministischen Bottom-up Automaten M, so dass L = L(M).
(Beweisidee : Teilmengenkonstruktion)
Berechnung bei Top-down Automaten
and
and not
1 0 0
q1 q1
not
q0 q0
q0 q0
q1 q0 q1
ok ok X
q0 q1
q1 q0 q0
ok ok ok
• det. Bottom-up kann Top-down nichtdet. sein (und umgekehrt!)
• Top-down werden genau dieselben Bäume erkannt
Deterministische Top-down Automaten
Definition: Ein Top-down Automat heißt deterministisch, wenn es in Δ keine Regel gibt, bei der die rechte Seite mehr als eine Zustandsmenge hat und |F| < 2 .
Satz : Es existieren erkennbare Sprachen , die nicht von einem deterministischen Top-down Automat erkannt werden können.
Sprache, die det. Top-down nicht erkannt werden kann
not
and
0 1
not
and
1 0
not
and
1 1
a
b
c d
a
b
c d
a
b
c d
ist in Sprache
ist in Sprache
ist NICHT in Sprache
(0,c) -> ε
(1,d) -> ε
(1,c) -> ε
(0,d) -> εwird akzeptiert
DEA -> det. Top-down Automaten
Aus DEA M=(Q, Σ, Δ, S, F) (klassische Darstellung) konstruiere Baumautomaten (Q, Σ‘, Δ‘, F‘) mit :
• Buchstaben aus Σ -> unäre Funktionssymbole
• zusätzliche Konstante # (symbolisiert Wortende)
• F‘ = S
• Δ‘ = Δ plus Regeln (q, #) für alle q aus F
a
b
a
#
aba
DEA -> det. Top-down Automaten
q0
q2
q1
ba
a
b ba
a
b
b
a
b a
#
q0
q0
q1
q1
q2 q1
q2
Übersicht Sprachenklassen
Sprachen von deterministischen
Top-down Automaten
erkennbar = von Bottom-up- oder nicht-deterministischen Top-down Automaten akzeptierte Sprachen
DEA/NEA-Sprachen
erkennbare Sprachen
Abschlusseigenschaften
Satz: Erkennbare Sprachen sind abgeschlossen unter Schnitt, Vereinigung und Komplementbildung.
Satz: Die Menge der Sprachen von det. Top-down Automaten ist abgeschlossen unter Schnitt und Vereinigung.
Entscheidungsprobleme
Membership LOGTIME-complete
Uniform Membership
linear für det., polynomiell für nichtdet. Automaten
Emptiness linear
Intersection non-emptiness
EXPTIME-complete
Finiteness polynomiell
Emptiness of the complement
EXPTIME-complete
Equivalence EXPTIME-complete
Singleton polynomiell
Unranked Automaten [Thatcher, 1967]
• jedes σ aus Σ kann beliebig viele Nachfolger haben
• Regeln in Δ beliebige reguläre Ausdrücke (mit Zeichenmenge Q)
Automat für boolesche Ausdrücke mit ∧,∨ mit beliebig vielen Kindern :Σ ={∧,∨,0,1}
Q={q0, q1}, F={q1}Δ= { (q0,0) -> ε; (q1,1) -> ε; (q0, ∧) -> (0∪1)*0(0∪1)*; (q1, ∧) -> 1*; (q0, ∨) -> 0*; (q1, ∨) -> (0∪1)*1(0∪1)* }
∨
∨ ∧ ∨
0 1 0 1 0
q1
q1 q0 q0
q0 q1 q0 q1 q0
XPATH -> Unranked Automat
Baue Automat für Anfrage /a//b[/a]//b
(/a//b[/a]//b, a) -> Q*(// b[/a]//b)Q*
(//b[/a]//b, b) -> Q*(//b[/a]//b)Q*
∪ Q* /a Q* //b Q*
∪ Q* //b Q* /a Q*
∪ Q*(/a//b)Q*
(/a//b,a) -> Q* //b Q*
(//b,a) -> Q* //b Q*
(//b,b) -> Q*
(/a,a) -> Q*
a
a a
b b a
b a
/a//b[/a]//b
//b[/a]//b /a
//b //b[/a]//b /a
//b /a
Unranked Baum -> Binärer Baum
• alle Symbole zweistellige Prädikate
• # neue Konstante für Blätter
• links Unterbäume, rechts nächstes Kind des Vaters
a
a bb
a b a
a
a #
a b
# # b#
b #
a#
# #
Kodierung
Dekodierung
Automaten auf Baumtupeln
f
f g
b f a
b a
f
f a
g g
b a
ff
ff ga
bg fg a# ##
#b ## ba a# ## ##
## ## ## ## ## ##
• Tupel von Zeichen -> binäre Funktionssymbole
• ## einzige Konstante
Zylindrifikation (an Stelle i)• Tupel um eins erweitern vor i-ter Stelle
Aus (q, s1...si-1si...sk) -> REGEXP1
für jedes σ aus Σ eine Regel
(q, s1...si-1σsi...sk) -> REGEXP1
• erzeugt evtl. nichtdet. Automaten (nur bei Bottom-up)
• Regelmenge wird größer um Faktor | Σ |
Projektion (an Stelle i)• Tupel um eins verkleinern an i-ter Stelle
Aus Regeln (q, s1...si-1σ1si+1...sk) -> REGEXP1
...
(q, s1...si-1σmsi+1...sk) -> REGEXPm
wird eine Regel
(q, s1...si-1 si+1...sk) -> REGEXP1 ∪ ... ∪ REGEXPm
• erzeugt evtl. nichtdet. Automaten (nur bei Top-down)
• Regelmenge wird kleiner
Einfaches Beispiel für Tupelautomaten
• Automat, der { [t,t] | t ist Σ-Baum } erkennt
mit Σ = {f/2, g/1, a/1}Q = {q}
F = {q}
(q, ##) -> ε
(q, aa) -> q
(q, gg) -> q
(q, ff) -> q
Referenzen
• H.Comon, M.Dauchet, R.Gilleron, F.Jacquemard, D.Lugiez, S.Tison and M.Tommasi : Tree Automata and its Applications Kap. 1, 3
Online Version: www . grappa. univ-lille3. fr/ tata
(1997, überarbeitete Fassung 2002)
• Frank Neven : Automata Theory for XML researchers, University of Limburg, 2002
• R.Wilhelm, D.Maurer : Übersetzerbau, Springer 1992(2.Version 1997)
ENDE
Danke fürs Zuhören!