summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTimotej Lazar <timotej.lazar@fri.uni-lj.si>2016-05-18 19:30:33 +0200
committerTimotej Lazar <timotej.lazar@fri.uni-lj.si>2016-05-18 19:33:14 +0200
commit4973979e40dfdc26dafe1cdeddf8e0bce859ba5d (patch)
tree58fd0d205f6ac20f3bf5a52cf6247b5fa577589f
parent025254ce93f7ce8b4d175dcb85d228506202583c (diff)
Prolog: add introduction for DCG group
-rw-r--r--prolog/problems/dcg/intro_sl.html301
-rw-r--r--prolog/problems/dcg/sl.py7
-rw-r--r--prolog/problems/dcg/syntax_tree.dot40
-rw-r--r--prolog/problems/dcg/syntax_tree.svg133
4 files changed, 480 insertions, 1 deletions
diff --git a/prolog/problems/dcg/intro_sl.html b/prolog/problems/dcg/intro_sl.html
new file mode 100644
index 0000000..ae94e73
--- /dev/null
+++ b/prolog/problems/dcg/intro_sl.html
@@ -0,0 +1,301 @@
+<!DOCTYPE html>
+<html lang="sl">
+<head>
+ <meta charset="utf-8" />
+ <title>Prolog: Gramatike (DCG)</title>
+ <link rel="stylesheet" type="text/css" href="../style.css" />
+</head>
+<body>
+
+<h1>Prolog: Gramatike (DCG)</h1>
+<p>
+Kako se ljudje sporazumevamo med seboj? Z jeziki, seveda. No, saj obstajajo
+tudi drugi načini komunikacije, a je vendarle jezik tisti osrednji,
+najpogostejši, način. In kako se sporazumevamo z računalnikom, kako mu
+razložimo, kaj naj naredi? Prav tako z jeziki, pa čeprav programskimi. Saj tako
+velike razlike med naravnimi in programskimi jeziki niti ni, le da so slednji
+bolj formalizirani, bolj natančni, bi lahko rekli. In prav vsi jeziki temeljijo na
+<em>slovnici</em> oz. <em>gramatiki</em>. Ta natančno opredeli, katere besede
+(včasih jim pravimo tudi stavki) so slovnično pravilne (so elementi jezika) in
+katere niso (niso elementi danega jezika).
+</p>
+
+<p>
+Gramatiko jezika navadno zapišemo v obliki množice produkcij oz. preslikovalnih
+pravil. Naredimo to kar na primeru. Imejmo naslednjo množico (dveh) pravil:
+</p>
+<pre>
+s --> []. % pravilo #1
+s --> [a,a], s. % pravilo #2
+</pre>
+<p>
+Medklic: Pravila načeloma niso videti kot prologov program, a v resnici jih
+prolog razume in interno pretvori v kodo, kot si je vajen. A danes se v to ne
+bomo spuščali, ker niti ni pomembno.
+</p>
+
+<p>
+Poglejmo si sestavne dele enega pravila in kako ga razumemo ter uporabljamo. Za
+primer vzemimo pravilo #2 zgoraj. Puščica (<code>--></code>) nam pravilo
+razdeli na levi in desni del. Pomeni pa naslednje: simbol na levi strani
+preslika v to, kar je na desni. Torej naše konkretno pravilo pomeni „zamenjaj
+simbol <code>s</code> s seznamom <code>[a,a]</code> in simbolom
+<code>s</code>“. Na enak način pravilo #1 pomeni „zamenjaj simbol
+<code>s</code> s praznim seznamom“.
+</p>
+
+<p>
+Zakaj so nekatere stvari pisane v seznamih in nekatere ne? Razlika je zelo
+pomembna: tistemu, kar je pisano v seznamih (npr. <code>[a,a]</code>), bomo
+rekli končni simboli ali terminali, simbolom izven seznamov (npr.
+<code>s</code>) pa nekončni simboli oz. neterminali. Nekončne simbole gramatike
+moramo vedno preslikati še naprej, medtem ko končnih simbolov ne moremo več
+preslikati naprej – od tu tudi njihovo poimenovanje. Ko si nekoč v šoli delal
+stavčno analizo pri pouku slovenščine, si stavek verjetno razdelil na
+samostalnik, glagol in podobne sintaktične elemente – to so nekončni simboli.
+Končni simboli pa so konkretni primeri teh elementov: npr. glagol
+„programirati“.
+</p>
+
+<p>
+DCG je le en izmed možnih zapisov gramatike. Na levi strani pravil v DCG se
+vedno pojavlja en in samo en nekončni simbol. Na desni strani je lahko poljubno
+zaporedje končnih in nekončnih simbolov, ločenih z vejicami. Slednje pomenijo
+konjunkcijo, kot smo že vajeni. Pravil je lahko poljubno mnogo – katero bomo
+uporabili v nekem konkretnem primeru, je stvar izbire. Ko smo že pri
+konjunkciji: podpičje tudi tu pomeni disjunkcijo. Zgornji dve pravili bi lahko
+zapisali tudi takole:
+</p>
+<pre>
+s --> [] ; [a,a], s.
+</pre>
+<p>
+Oziroma v duhu drugih jezikov za opis gramatik, kot je npr. BNF, tudi takole:
+</p>
+<pre>
+s --> [] | [a,a], s.
+</pre>
+
+<p>
+Skratka tudi navpičnica pomeni disjunkcijo: neterminal <code>s</code> se lahko
+preslika ali v prazen seznam ali pa v seznam dveh terminalov <code>a</code> in
+v neterminal <code>s</code>.
+</p>
+
+<p>
+Prav, sedaj poznamo obliko zapisa. Kaj pa lahko s tem počnemo oz. kakšno
+povezavo ima to z jeziki? Pri vsaki gramatiki imamo tipično določen tudi nek
+začetni nekončni simbol, pri našem primeru bo to kar simbol <code>s</code>, ki
+je tudi edini nekončni simbol. Izpeljavo poljubne besede oz. stavka v jeziku
+začnemo s tem simbolom in na njem v poljubnem redu uporabljamo preslikovalna
+pravilo dokler ne dobimo rezultata sestavljenega samo iz končnih simbolov.
+Poglejmo nekaj primerov.
+</p>
+
+<pre>
+Primer 1: <strong>s</strong> --(2)--> aa<strong>s</strong> --(1)--> aa
+</pre>
+
+<p>
+Za lažji prikaz so odebeljeno prikazani nekončni simboli, z normalno pisavo pa
+končni simboli. V prvem primeru na začetnem simbolu najprej uporabimo pravilo
+#2 in dobimo <code>aa<strong>s</strong></code>, nato pa na tem pravilo #1 (na
+neterminalu <code><strong>s</strong></code>, seveda) in dobimo <code>aa</code>.
+Ker po drugem koraku nimamo v rezultatu več nobenih nekončnih simbolov, smo
+zaključili. Beseda oz. stavek <code>aa</code> je sintaktično pravilen stavek v
+jeziku, ki ga definira naša zgornja gramatika.
+</p>
+
+<pre>
+Primer 2: <strong>s</strong> --(2)--> aa<strong>s</strong> --(2)--> aaaa<strong>s</strong> --(1)--> aaaa
+</pre>
+
+<p>
+V tem primeru smo izpeljali stavek <code>aaaa</code>. Če malce pomislimo,
+opazimo, da naša gramatika generira prazen stavek (nič <code>a</code>-jev),
+<code>aa</code>, <code>aaaa</code>, <code>aaaaaa</code>, itd. Skratka, naši
+stavki so vedno sestavljeni iz sodega števila <code>a</code>-jev. Lahko se še
+tako trudiš, a ti iz začetnega simbola <code><strong>s</strong></code> ne bo
+uspelo izpeljati stavka z lihim številom <code>a</code>-jev. Pravzaprav lahko
+ta razmislek peljemo še malce dlje. Vsak stavek lahko izpeljemo le na en sam
+način! Za stavek z n <code>a</code>-ji moramo najprej n/2-krat uporabiti
+pravilo #2 in na koncu enkrat pravilo #1.
+</p>
+
+<p>
+Preden to misel razvijemo naprej, naj odgovorim še na vprašanje, kako lahko
+zgornje stvari poskusiš v prologu. Preposto, zgornjo gramatiko prepišeš kot
+program (kar v resnici je!) in poganjaš poizvedbe v konzoli takole:
+</p>
+<pre>
+?- s(Word, []).
+Word = [] ;
+Word = [a,a] ;
+Word = [a,a,a,a] ;
+…
+</pre>
+
+<p>
+Poizvedbo torej pokličeš z začetnim simbolom (ki ga prolog v resnici interno
+prevede v predikat, kot si jih vajen), ki mu podaš dva argumenta. V bistvu je
+ta par argumentov en sam argument, ki tvori besedo (oz. stavek), ki jo bo
+gramatika generirala. Zakaj tak zapis z dvema seznamoma? Gre za razliko
+seznamov – če drugega pustiš praznega, bo prvi ostal tak, kot je; tako bomo
+večinoma pustili. Tak zapis je posledica učinkovite implementacije. Ko prolog
+generira besede nekega jezika, to počne s konkatenacijo seznamov. Za slednjo si
+videl, da je časovne zahtevnosti O(n), a se jo da s trikom razlike seznamov
+narediti v času O(1).
+</p>
+
+<p>
+Kot si že vajen, stvari delujejo v več smeri. Zgoraj smo gramatiko uporabili za
+generiranje besed jezika. Bolj običajna uporaba pa je v drugi smeri:
+računalniški prevajalniki tipično preverjajo, ali je podana beseda sintaktično
+pravilna. To pomeni, ali jo lahko izpeljemo z uporabo pravil dane gramatike.
+Spodnji poizvedbi sta tak primer uporabe.
+</p>
+
+<pre>
+?- s([a,a], []).
+true
+?- s([a,a,a,a,a], []).
+false
+</pre>
+
+<h2>Dvoumnost gramatik</h2>
+<p>
+Zakaj smo posebej izpostavili, da lahko nek stavek izpeljemo le na en način?
+Ker je to verjetno ena najpomembnejših lastnosti gramatik! Predpostavimo, da
+imamo poleg zgornjih dveh pravil še tretje:
+</p>
+<pre>
+s --> []. % pravilo #1
+s --> [a,a], s. % pravilo #2
+s --> s, [a,a]. % pravilo #3
+</pre>
+
+<p>
+Sedaj lahko stavek <code>aaaa</code> izpeljem na več kot en način, npr. takole:
+</p>
+<pre>
+Način 1: <strong>s</strong> --(2)--> aa<strong>s</strong> --(2)--> aaaa<strong>s</strong> --(1)--> aaaa
+Način 2: <strong>s</strong> --(3)--> <strong>s</strong>aa --(2)--> aa<strong>s</strong>aa --(1)--> aaaa
+</pre>
+
+<p>
+Kaj je v tem tako strašnega? Je morda problem v tem, da imamo več izbire? Ne,
+problem je v tem, da isti stavek (<code>aaaa</code>) lahko pomeni več stvari.
+Če računalniku rečeš „Prištej ena.“, ne želiš, da to pomeni več različnih
+stvari, kajne? Predstavljaj si, da bi te računalnik razumel malce po svoje: saj
+bi bilo zabavno, ampak jaz si tako sprogramiranega avtopilota na primer ne
+želim kaj preveč.
+</p>
+
+<p>
+Omenili smo pomen in da je pomen tesno povezan z izpeljavo (zaporedjem uporabe
+konkretnih preslikovalnih pravil gramatike). Tako je, kasneje bomo videli, da
+tipično vsaki preslikavi pripišemo pomen.
+</p>
+
+<p>
+Izpeljavo besed v jeziku tipično predstavimo z drevesi izpeljave. Tako bolj
+pregledno pokažemo tisto kar smo zgoraj naredili s puščicami v eni vrstici. Pri
+več neterminalih tako točno vemo kateri neterminal smo preslikali v kaj.
+Primera zgornjih izpeljav sta podana spodaj. Končni rezultat preberemo z levim
+obhodom drevesa, posamezne sezname pa konkateniramo med seboj.
+</p>
+
+<figure>
+ <img src="syntax_tree.svg" />
+ <figcaption>Različni drevesi izpeljave za besedo <code>aaaa</code></figcaption>
+</figure>
+
+<h2>Dodajanje kode v gramatiko</h2>
+<p>
+Ker v našem primeru gramatiko uporabljamo znotraj programskega jezika
+(prologa), nam seveda pride na misel, da bi lahko znotraj gramatike uporabili
+tudi običajne prologove predikate. To je dejansko mogoče in nam v nekaterih
+primerih pride precej prav. Poglejmo, kako to naredimo na naslednjem primeru.
+Recimo, da želimo definirati gramatiko za jezik, kjer imamo večjo izhodno
+abecedo kot samo <code>a</code> v prejšnjem primeru, a želimo, da se vse črke
+vedno podvajajo.
+</p>
+
+<pre>
+s --> []. % pravilo #1
+s --> letter, s. % pravilo #2
+letter --> [X,X], { member(X, [a,b,c,d, …, z]) }. % pravilo #3
+</pre>
+
+<p>
+Pravilo #3 je zanimivo: velike črke nam kot vedno v prologu tudi tu
+predstavljajo spremenljivke. Rezultat tega pravila je seznam oblike
+<code>[X,X]</code>. S predikatom <code>member/2</code> pa generiramo vse
+možnosti za <code>X</code>: v tem primeru vse črke abecede od <code>a</code> do
+<code>z</code>. Predikat <code>member/2</code> smo zapisali znotraj zavitih
+oklepajev. V tem primeru ne gre za omejitve kot pri CLP(R), ampak prologu na ta
+način povemo, da gre za običajno prologovsko kodo. Tako lahko uporabljamo
+poljubne predikate znotraj pravil DCG. Celo CLP(R) lahko uporabimo, tako da
+znotraj zavitih oklepajev zapišemo še ene zavite oklepaje.
+</p>
+
+<h2>V kakšnem vrstnem redu prolog bere pravila?</h2>
+<p>
+Vrstni red uporabe pravil je tak, kot smo ga že vajeni pri prologu. Ta poskuša
+pravila za posamezni neterminal od zgoraj navzdol. In poskuša vse, torej zopet
+generira vse možne izpeljave eno za drugo z mehanizmom vračanja, če seveda tako
+zahtevamo.
+</p>
+
+<p>
+Vrstni red preslikave znotraj posameznega pravila je od leve proti desni.
+Vrstni red je pomemben. Kodo (z zavitimi oklepaji) lahko vključimo na poljubno
+mesto in jo ločimo z vejicami. Izvedla se bo takrat, ko bo prolog nanjo
+naletel, torej zopet od leve proti desni.
+</p>
+
+<h2>Dodatni argumenti in pomen</h2>
+<p>
+Nekončnim simbolom gramatike lahko dodajamo dodatne argumente. Ti nam lahko
+služijo za različne stvari, a največkrat z njimi definiramo pomen besed, ki jih
+generira oz. razpozna dana gramatika.
+</p>
+
+<p>
+Definirajmo gramatiko, ki sprejme/generira poljubno zaporedje črk
+<code>a</code> in <code>b</code>, njen pomen pa naj bo razlika v številu teh
+črk. Z malo domišljije lahko rečemo, da gre za izid nogometne tekme:
+<code>a</code> pomeni gol prve ekipe, <code>b</code> pa gol druge ekipe.
+Neterminal <code>game</code> naj bo začetni simbol te gramatike.
+</p>
+
+<pre>
+game(0) --> [].
+game(Diff) --> goal(Diff1), game(Diff2), {Diff is Diff1 + Diff2}.
+goal( 1) --> [a].
+goal(-1) --> [b].
+</pre>
+
+<p>
+Pomen lahko razumemo takole. Če je tekma brez golov (oz. ko v rekurziji pridemo
+do praznega seznama golov), je razlika 0. Vsak <code>a</code> pomeni gol za
+prvo ekipo in je vreden +1, vsak <code>b</code> pa gol za drugo ekipo in je
+vreden -1. Pravilo, da je tekma sestavljena iz gola in potem še poljubno golov
+v nadaljevanju, pa pove, da je razlika taka kot je v nadaljevanju, ki ji
+prištejemo še vrednost gola: plus ali minus 1. Kot vidiš, je precej podobno,
+kot če bi to sprogramili v prologu z rekurzijo. Pravzaprav se prevede v točno
+to! Pomembno je, da smo dali kodo znotraj zavitih oklepajev na konec pravila
+#2. Do takrat namreč že izvemo vrednosti za <code>Diff1</code> in
+<code>Diff2</code>.
+</p>
+
+<p>
+Primer uporabe:
+</p>
+<pre>
+?- game(Diff, [a,b,a,a], []). % končni rezultat 3-1 za prvo ekipo
+Diff = 2.
+</pre>
+
+</body>
+</html>
diff --git a/prolog/problems/dcg/sl.py b/prolog/problems/dcg/sl.py
index 2e5a381..3c1deb7 100644
--- a/prolog/problems/dcg/sl.py
+++ b/prolog/problems/dcg/sl.py
@@ -1,2 +1,7 @@
name = 'Gramatike (DCG)'
-description = 'Sestavljanje in testiranje gramatik, od preprostih do precej realističnih; podlaga za prevajalnike.'
+description = '''\
+<p>
+<a target="_blank" href="[%@resource intro_sl.html%]">Gramatike</a>
+– sestavljanje in testiranje gramatik, od preprostih do precej realističnih;
+podlaga za prevajalnike.
+</p>'''
diff --git a/prolog/problems/dcg/syntax_tree.dot b/prolog/problems/dcg/syntax_tree.dot
new file mode 100644
index 0000000..54238d2
--- /dev/null
+++ b/prolog/problems/dcg/syntax_tree.dot
@@ -0,0 +1,40 @@
+digraph {
+ ordering=out;
+ pad=0;
+ ranksep=0.3;
+
+ node [fontname="sans",height=0.2,penwidth=0];
+ edge [fontname="sans",fontsize=8,arrowsize=0.6];
+
+ subgraph {
+ sa1 [label="s"];
+ sa2 [label="s"];
+ sa3 [label="s"];
+
+ aa1 [label="aa",fontname="mono"];
+ aa2 [label="aa",fontname="mono"];
+ ea [label="[]",fontname="mono"];
+
+ sa1 -> aa1 [label=" 2"];
+ sa1 -> sa2 [label=" 2"];
+ sa2 -> aa2 [label=" 2"];
+ sa2 -> sa3 [label=" 2"];
+ sa3 -> ea [label=" 1"];
+ }
+
+ subgraph {
+ sb1 [label="s"];
+ sb2 [label="s"];
+ sb3 [label="s"];
+
+ ab1 [label="aa",fontname="mono"];
+ ab2 [label="aa",fontname="mono"];
+ eb [label="[]",fontname="mono"];
+
+ sb1 -> sb2 [label=" 3"];
+ sb1 -> ab1 [label=" 3"];
+ sb2 -> ab2 [label=" 2"];
+ sb2 -> sb3 [label=" 2"];
+ sb3 -> eb [label=" 1"];
+ }
+}
diff --git a/prolog/problems/dcg/syntax_tree.svg b/prolog/problems/dcg/syntax_tree.svg
new file mode 100644
index 0000000..a1a8083
--- /dev/null
+++ b/prolog/problems/dcg/syntax_tree.svg
@@ -0,0 +1,133 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
+ "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by graphviz version 2.38.0 (20140413.2041)
+ -->
+<!-- Title: %3 Pages: 1 -->
+<svg width="332pt" height="223pt"
+ viewBox="0.00 0.00 332.00 223.11" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
+<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(0 223.108)">
+<title>%3</title>
+<polygon fill="white" stroke="none" points="0,-0 0,-223.108 332,-223.108 332,-0 0,-0"/>
+<!-- sa1 -->
+<g id="node1" class="node"><title>sa1</title>
+<ellipse fill="none" stroke="black" stroke-width="0" cx="53" cy="-206.844" rx="27" ry="16.0303"/>
+<text text-anchor="middle" x="53" y="-203.144" font-family="sans" font-size="14.00">s</text>
+</g>
+<!-- sa2 -->
+<g id="node2" class="node"><title>sa2</title>
+<ellipse fill="none" stroke="black" stroke-width="0" cx="99" cy="-143.317" rx="27" ry="16.0303"/>
+<text text-anchor="middle" x="99" y="-139.617" font-family="sans" font-size="14.00">s</text>
+</g>
+<!-- sa1&#45;&gt;sa2 -->
+<g id="edge2" class="edge"><title>sa1&#45;&gt;sa2</title>
+<path fill="none" stroke="black" d="M63.6689,-191.574C69.9392,-183.187 77.9454,-172.479 84.7505,-163.377"/>
+<polygon fill="black" stroke="black" points="86.478,-164.573 88.3889,-158.51 83.1142,-162.058 86.478,-164.573"/>
+<text text-anchor="middle" x="82.5" y="-173.181" font-family="sans" font-size="8.00"> 2</text>
+</g>
+<!-- aa1 -->
+<g id="node4" class="node"><title>aa1</title>
+<ellipse fill="none" stroke="black" stroke-width="0" cx="27" cy="-143.317" rx="27" ry="16.0303"/>
+<text text-anchor="middle" x="27" y="-139.617" font-family="mono" font-size="14.00">aa</text>
+</g>
+<!-- sa1&#45;&gt;aa1 -->
+<g id="edge1" class="edge"><title>sa1&#45;&gt;aa1</title>
+<path fill="none" stroke="black" d="M46.7061,-190.95C43.4336,-183.206 39.3803,-173.614 35.8023,-165.147"/>
+<polygon fill="black" stroke="black" points="37.6865,-164.211 33.4165,-159.502 33.8177,-165.846 37.6865,-164.211"/>
+<text text-anchor="middle" x="45.5" y="-173.181" font-family="sans" font-size="8.00"> 2</text>
+</g>
+<!-- sa3 -->
+<g id="node3" class="node"><title>sa3</title>
+<ellipse fill="none" stroke="black" stroke-width="0" cx="135" cy="-79.7904" rx="27" ry="16.0303"/>
+<text text-anchor="middle" x="135" y="-76.0904" font-family="sans" font-size="14.00">s</text>
+</g>
+<!-- sa2&#45;&gt;sa3 -->
+<g id="edge4" class="edge"><title>sa2&#45;&gt;sa3</title>
+<path fill="none" stroke="black" d="M107.531,-127.736C112.284,-119.614 118.267,-109.388 123.435,-100.555"/>
+<polygon fill="black" stroke="black" points="125.312,-101.506 126.53,-95.2667 121.687,-99.3849 125.312,-101.506"/>
+<text text-anchor="middle" x="123.5" y="-109.654" font-family="sans" font-size="8.00"> 2</text>
+</g>
+<!-- aa2 -->
+<g id="node5" class="node"><title>aa2</title>
+<ellipse fill="none" stroke="black" stroke-width="0" cx="63" cy="-79.7904" rx="27" ry="16.0303"/>
+<text text-anchor="middle" x="63" y="-76.0904" font-family="mono" font-size="14.00">aa</text>
+</g>
+<!-- sa2&#45;&gt;aa2 -->
+<g id="edge3" class="edge"><title>sa2&#45;&gt;aa2</title>
+<path fill="none" stroke="black" d="M90.4685,-127.736C85.7161,-119.614 79.7328,-109.388 74.5646,-100.555"/>
+<polygon fill="black" stroke="black" points="76.3129,-99.3849 71.4703,-95.2667 72.6879,-101.506 76.3129,-99.3849"/>
+<text text-anchor="middle" x="87.5" y="-109.654" font-family="sans" font-size="8.00"> 2</text>
+</g>
+<!-- ea -->
+<g id="node6" class="node"><title>ea</title>
+<ellipse fill="none" stroke="black" stroke-width="0" cx="135" cy="-16.2635" rx="27" ry="16.0303"/>
+<text text-anchor="middle" x="135" y="-12.5635" font-family="mono" font-size="14.00">[]</text>
+</g>
+<!-- sa3&#45;&gt;ea -->
+<g id="edge5" class="edge"><title>sa3&#45;&gt;ea</title>
+<path fill="none" stroke="black" d="M135,-63.2645C135,-55.9222 135,-47.0305 135,-39.0293"/>
+<polygon fill="black" stroke="black" points="137.1,-38.5712 135,-32.5712 132.9,-38.5712 137.1,-38.5712"/>
+<text text-anchor="middle" x="138.5" y="-46.1269" font-family="sans" font-size="8.00"> 1</text>
+</g>
+<!-- sb1 -->
+<g id="node7" class="node"><title>sb1</title>
+<ellipse fill="none" stroke="black" stroke-width="0" cx="287" cy="-206.844" rx="27" ry="16.0303"/>
+<text text-anchor="middle" x="287" y="-203.144" font-family="sans" font-size="14.00">s</text>
+</g>
+<!-- sb2 -->
+<g id="node8" class="node"><title>sb2</title>
+<ellipse fill="none" stroke="black" stroke-width="0" cx="233" cy="-143.317" rx="27" ry="16.0303"/>
+<text text-anchor="middle" x="233" y="-139.617" font-family="sans" font-size="14.00">s</text>
+</g>
+<!-- sb1&#45;&gt;sb2 -->
+<g id="edge6" class="edge"><title>sb1&#45;&gt;sb2</title>
+<path fill="none" stroke="black" d="M275.016,-192.189C267.395,-183.507 257.435,-172.158 249.125,-162.69"/>
+<polygon fill="black" stroke="black" points="250.487,-161.058 244.951,-157.934 247.33,-163.829 250.487,-161.058"/>
+<text text-anchor="middle" x="267.5" y="-173.181" font-family="sans" font-size="8.00"> 3</text>
+</g>
+<!-- ab1 -->
+<g id="node10" class="node"><title>ab1</title>
+<ellipse fill="none" stroke="black" stroke-width="0" cx="305" cy="-143.317" rx="27" ry="16.0303"/>
+<text text-anchor="middle" x="305" y="-139.617" font-family="mono" font-size="14.00">aa</text>
+</g>
+<!-- sb1&#45;&gt;ab1 -->
+<g id="edge7" class="edge"><title>sb1&#45;&gt;ab1</title>
+<path fill="none" stroke="black" d="M291.449,-190.635C293.64,-183.149 296.318,-173.995 298.713,-165.807"/>
+<polygon fill="black" stroke="black" points="300.807,-166.127 300.477,-159.779 296.776,-164.948 300.807,-166.127"/>
+<text text-anchor="middle" x="301.5" y="-173.181" font-family="sans" font-size="8.00"> 3</text>
+</g>
+<!-- sb3 -->
+<g id="node9" class="node"><title>sb3</title>
+<ellipse fill="none" stroke="black" stroke-width="0" cx="279" cy="-79.7904" rx="27" ry="16.0303"/>
+<text text-anchor="middle" x="279" y="-76.0904" font-family="sans" font-size="14.00">s</text>
+</g>
+<!-- sb2&#45;&gt;sb3 -->
+<g id="edge9" class="edge"><title>sb2&#45;&gt;sb3</title>
+<path fill="none" stroke="black" d="M243.669,-128.047C249.939,-119.66 257.945,-108.952 264.751,-99.8496"/>
+<polygon fill="black" stroke="black" points="266.478,-101.046 268.389,-94.9831 263.114,-98.5311 266.478,-101.046"/>
+<text text-anchor="middle" x="262.5" y="-109.654" font-family="sans" font-size="8.00"> 2</text>
+</g>
+<!-- ab2 -->
+<g id="node11" class="node"><title>ab2</title>
+<ellipse fill="none" stroke="black" stroke-width="0" cx="207" cy="-79.7904" rx="27" ry="16.0303"/>
+<text text-anchor="middle" x="207" y="-76.0904" font-family="mono" font-size="14.00">aa</text>
+</g>
+<!-- sb2&#45;&gt;ab2 -->
+<g id="edge8" class="edge"><title>sb2&#45;&gt;ab2</title>
+<path fill="none" stroke="black" d="M226.706,-127.423C223.434,-119.679 219.38,-110.087 215.802,-101.62"/>
+<polygon fill="black" stroke="black" points="217.686,-100.684 213.417,-95.9746 213.818,-102.319 217.686,-100.684"/>
+<text text-anchor="middle" x="225.5" y="-109.654" font-family="sans" font-size="8.00"> 2</text>
+</g>
+<!-- eb -->
+<g id="node12" class="node"><title>eb</title>
+<ellipse fill="none" stroke="black" stroke-width="0" cx="279" cy="-16.2635" rx="27" ry="16.0303"/>
+<text text-anchor="middle" x="279" y="-12.5635" font-family="mono" font-size="14.00">[]</text>
+</g>
+<!-- sb3&#45;&gt;eb -->
+<g id="edge10" class="edge"><title>sb3&#45;&gt;eb</title>
+<path fill="none" stroke="black" d="M279,-63.2645C279,-55.9222 279,-47.0305 279,-39.0293"/>
+<polygon fill="black" stroke="black" points="281.1,-38.5712 279,-32.5712 276.9,-38.5712 281.1,-38.5712"/>
+<text text-anchor="middle" x="282.5" y="-46.1269" font-family="sans" font-size="8.00"> 1</text>
+</g>
+</g>
+</svg>