Mod-7.1 7 Modellierung von Abläufen 7.1 Endliche Automaten Endlicher Automat: Formaler Kalkül zur Spezifikation von realen oder abstrakten Maschinen. Sie * reagieren auf äußere Ereignisse, * ändern ihren inneren Zustand, * produzieren ggf. Ausgabe. Endliche Automaten werden eingesetzt, um * das Verhalten realer Maschinen zu spezifizieren, z. B. Getränkeautomat, * das Verhalten von Software-Komponenten zu spezifizieren, z. B. Reaktionen von Benutzungsoberflächen auf Bedienereignisse, * Sprachen zu spezifizieren: Menge der Ereignis- oder Symbolfolgen, die der Automat akzeptiert, z. B. Schreibweise von Bezeichnern und Zahlwerten in Programmen Zunächst definieren wir nur die Eingabeverarbeitung der Automaten; das Erzeugen von Ausgabe fügen wir später hinzu. (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 701 Ziele: Charakterisierung endlicher Automaten in der Vorlesung: Erläuterungen dazu nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.1 -------------------------------------------------------------------------------- Mod-7.2 Zwei einführende Beispiele Endlicher Automat definiert eine Sprache, Endlicher Automat spezifiziert das d. h. eine Menge von Wörtern. Verhalten einer Maschine. Ein Wort ist eine Folge von Zeichen. Hier: einfacher Getränkeautomat: Hier: Bezeichner in Pascal-Programmen: GetränkNehmen Buchstabe 2EUR 2 0 1EUR Buchstabe 1EUR 0 1 1 GeldRück GeldRück Ziffer Akzeptiert Folgen von Buchstaben und Akzeptiert Folgen von Ereignissen zur Ziffern beginnend mit einem Buchstaben. Bedienung eines Getränkeautomaten Endliche Automaten können durch gerichtete, markierte Graphen dargestellt werden, Ablaufgraphen. (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 702 Ziele: Eindruck von Automaten und ihrer Darstellung in der Vorlesung: Informelle Erläuterungen zu * Zuständen, * Übergängen, * äußeren Ereignissen nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.1 -------------------------------------------------------------------------------- Mod-7.3 Alphabete Alphabet: Eine Menge von Zeichen zur Bildung von Zeichenfolgen, häufig mit Sigma bezeichnet. Wir betrachten hier nur endliche Alphabete, z. B. {0, 1} {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} {a, b, ..., z} Ein Wort über einem Alphabet Sigma ist eine Zeichenfolge aus Sigma * statt (a1, a2, ..., an) element Sigma * schreiben wir a1 a2 ... an, z. B. 10010 element {0, 1}* für die leere Folge schreiben wir auch epsilon (epsilon) (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 703 Ziele: Wörter über Alphabeten in der Vorlesung: Erläuterungen und Beispiele dazu nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.1 -------------------------------------------------------------------------------- Mod-7.4 Reguläre Ausdrücke Reguläre Ausdrücke beschreiben Mengen von Worten, die nach bestimmten Regeln aufgebaut sind. Seien F und G reguläre Ausdrücke, dann gilt regulärer Menge von Worten Erklärung Ausdruck a { a } Zeichen a als Wort epsilon { epsilon } das leere Wort F | G { f | f element F } union { g | g element G } Alternativen F G { f g | f element F, g element G } Zusammenfügen von Worten Fn { f1 f2 ... fn | für alle i element {1,..n}: fi element F } n Worte aus F F* { f1 f2 ... fn | n greaterequal 0 und für alle i element {1,..n}: fi element F } Folgen von Worten aus F F+ { f1 f2 ... fn | n greaterequal 1 und für alle i element {1,..n}: fi element F } nicht-leere Folgen von Worten aus F ( F ) F Klammerung Beispiele: 13 ( 1 | 0 )* 03 Bezeichner = B ( B | D )* mit B = a | b | ... | z und D = 0 | 1 | ... | 9 (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 704 Ziele: Einfache Beschreibung von Wortmengen kennenlernen in der Vorlesung: Erläuterungen zu * rekursiver Definition von regulären Ausdrücken, * Hintereinanderschreibung von Zeichen und Teilworten, * Folgen von Worten, * Alternativen, * Namen für reguläre Ausdrücke nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.1 Verständnisfragen: Unterscheiden Sie: * das leere Wort, * die leere Menge, * die Menge, die nur das leere Wort enthält. -------------------------------------------------------------------------------- Mod-7.5 Deterministischer endlicher Automat Deterministischer endlicher Automat (engl.: deterministic finite automaton, DFA): Quintupel A = (Sigma , Q, delta , q0, F) mit Sigma endliches Eingabealphabet Q endliche Menge von Zuständen delta Übergangsfunktion aus Q multiply Sigma -> Q q0 element Q Anfangszustand F reflexsubset Q Menge der Endzustände (akzeptierend) Wir nennen r = delta (q, a) Nachfolgezustand von q unter a. A heißt deterministisch, weil es zu jedem Paar (q, a), mit q element Q, a element Sigma , höchstens einen Nachfolgezustand delta (q, a) gibt, d. h. delta ist eine Funktion in Q. A heißt vollständig, wenn die Übergangsfunktion delta eine totale Funktion ist. (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 705 Ziele: Formale Definition verstehen in der Vorlesung: Erläuterungen zu * den Komponenten des 5-Tupels, * dem Begriff "deterministisch", * der Eigenschaft "vollständig" nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.1 -------------------------------------------------------------------------------- Mod-7.6 Gerichteter Graph zu endlichem Automaten Knoten: Zustände des Automaten; Anfangszustand und Endzustände werden speziell markiert Kanten: Übergangsfunktion, q -> r markiert mit a, genau dann wenn delta (q, a) = r Es gibt Kanten, die sich nur durch ihre Markierung unterscheiden, deshalb: Multigraph Beispiele von Mod-7.2: Sigma := Menge der ASCII-Zeichen Sigma := {1EUR, 2EUR, GeldRück, GetränkNehmen} Q := {0, 1} Q := {0, 1, 2} delta := a...zA...Z 0...9 sonstige delta := 1EUR 2EUR GeldRück GetränkNehmen 0 1 0 1 2 1 1 1 1 2 0 q 2 0 0 0 = 0 Buchstabe F = {1} q0 = 0 0 Buchstabe GetränkNehmen 1 F = {0} 2EUR 2 0 1EUR 1EUR Ziffer 1 Buchstabe, Ziffer GeldRück sind Namen reg. Ausdrücke GeldRück (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 706 Ziele: Graphdarstellung verstehen in der Vorlesung: * Übergangsfunktion ist als Tabelle angegeben * Markierung von Anfangs- und Endzuständen * Zusammenfassung von Zeichen mit gleichen Übergängen zu Zeichenklassen nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.1 -------------------------------------------------------------------------------- Mod - 7.7 Akzeptierte Sprache Die Zeichen einer Zeichenfolge bewirken nacheinander Zustandsübergänge in Automaten. Zustandsübergangsfunktion erweitert für Zeichenfolgen: Sei delta : Q x Sigma -> Q eine Übergangsfunktion für Zeichen, dann ist delta ^ : Q x Sigma asteriskmath minus > Q eine Übergangsfunktion für Wörter, rekursiv definiert: * Übergang mit dem leeren Wort: delta ^ (q, epsilon ) = q für alle q element Q * Übergang mit dem Wort wa: delta ^ (q, wa) = delta ( delta ^ (q, w), a) für alle q element Q, w element Sigma asteriskmath , a element Sigma Statt delta ^ schreiben wir meist auch delta . Sei A = (Sigma , Q, delta , q0, F) ein deterministischer endlicher Automat und w element Sigma asteriskmath . A akzeptiert das Wort w genau dann, wenn delta (q0, w) element F. Die Menge L(A) : = { w element Sigma asteriskmath arrowvertex delta ( q0, w) element F } heißt die von A akzeptierte Sprache. Beispiele für Sprachen, die von endlichen Automaten akzeptiert werden können: L1 = a+ b+ = union an bm L2 = Sigma asteriskmath n, m element Iota N Es gibt keinen endlichen Automaten, der L3 = union an bn n element Iota N akzeptiert. (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 707 Ziele: Sprache eines endlichen Automaten verstehen in der Vorlesung: Erläuterungen * zur Übergangsfunktion für Wörter, * zur Sprache des Automaten, * zu Beispielen In der Praxis werden Automaten meist nicht vollständig (siehe Mod-7.5) angegeben. Sie arbeiten dann nach der Regel des längsten Musters, d. h.: * Der Automat macht Übergänge, solange sie für die Eingabe definiert sind. * Der zuletzt durchlaufene Endzustand bestimmt das akzeptierte Wort. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.1 -------------------------------------------------------------------------------- Mod - 7.8 Beispiele: Endliche Automaten und ihre Sprachen a a 1. a* b a b a+b+ 4. Sigma 2. Sigma * a a a a 5. a3b3 3. a a+ b b b S 6. / * * / X * X = Sigma \ { *}, S = Sigma \ { /, *} Sprache: /* Sigma * */ (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 708 Ziele: Sprachen endlicher Automaten verstehen in der Vorlesung: Erläuterungen zur Sprache der Automaten nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.1 -------------------------------------------------------------------------------- Mod - 7.9 Nicht-deterministischer Automat Nicht-deterministisch (allgemein) : Es gibt mehrere Möglichkeiten der Entscheidung bzw. der Fortsetzung, es ist aber nicht festgelegt, welche gewählt wird. Nicht-deterministischer endlicher Automat: Die Übergangsfunktion delta kann einen Zustand q und ein Eingabezeichen a auf mehrere Nachfolgezustände abbilden delta : Q multiply Sigma -> Pow (Q). Welcher gewählt wird, ist nicht festgelegt. Sigma , Q, q0, F sind wie für deterministische endliche Automaten definiert. Erweiterung von delta auf Zeichenfolgen: Sei A = ( Sigma , Q, delta , q0, F) ein nicht-deterministischer endlicher Automat; dann ist delta ^ definiert: - Übergang mit dem leeren Wort: delta ^ (q, epsilon ) = { q } für alle q element Q - Übergang mit dem Wort wa: delta ^ (q, wa) = {q' element Q arrowvertex es gibt p element delta ^ (q, w): q'element delta (p, a)} für alle q element Q, w element Sigma asteriskmath , a element Sigma , d. h. die Menge aller Zustände, die man von q mit wa erreichen kann Wir schreiben meist delta für delta ^ Ein nicht-deterministischer endlicher Automat A akzeptiert ein Wort w gdw. delta (q0, w) intersection F notequal emptyset L(A) = {w element Sigma asteriskmath arrowvertex delta (q0, w) intersection F notequal emptyset } ist die von A akzeptierte Sprache. (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 709 Ziele: Nicht-Determiniertheit verstehen in der Vorlesung: Erläuterungen * zur Übergangsfunktion an Beispielen, * zur Erweiterung der Übergangsfunktion, * zur Nicht-Determiniertheit im Automaten und im allgemeinen. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.1 -------------------------------------------------------------------------------- Mod - 7.10 Nicht-deterministische und deterministische Automaten Satz: Sei L(A) die Sprache eines nicht-deterministischen Automaten. Dann gibt es einen deterministischen Automaten, der L(A) akzeptiert. Man kann aus einem nicht-deterministischen Automaten A = (Sigma , Q , delta , q0 , F) einen deterministischen A' = (Sigma , Q', delta ', q0', F') systematisch konstruieren: Jeder Zustand aus Q' repräsentiert eine Menge von Zuständen aus Q, d. h. Q' reflexsubset Pow(Q) Beispiel: nicht-deterministisch A deterministisch A' a {0,1} a a {0,1,2} a {0} a 0 a 1 2 b b b a b b {0,2} b Die Zahl der Zustände kann sich dabei exponentiell vergrößern. (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 710 Ziele: Zusammenhang der Automaten verstehen in der Vorlesung: (Zusammen mit Mod-7.11) * Zusammenhang: Zustand - Menge von Zuständen, * Beispiel erläutern. * L(A): Wörter über {a, b}*, deren zweitletztes Zeichen ein a ist. * Bei n-letztem Zeichen benötigt der deterministische Automat 2 hoch n Zustände. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.1 -------------------------------------------------------------------------------- Mod - 7.11 Konstruktion deterministischer Automaten Sei A ein nicht-deterministischer Automate A = (Sigma , Q , delta , q0 , F) daraus wird ein deterministischer Automat A' = (Sigma , Q', delta ', q0', F') systematisch konstruiert: Jeder Zustand aus Q' repräsentiert eine Menge von Zuständen aus Q, d. h. Q' reflexsubset Pow(Q) Konstruktionsschritte: 1. Anfangszustand: q0' = {q0} 2. Wähle einen schon konstruierten Zustand q' element Q' wähle ein Zeichen a element Sigma berechne r' = delta ' (q', a) = union q element q' delta (q, a) d. h. r' repräsentiert die Vereinigung aller Zustände, die in A von q unter a erreicht werden. r' wird Zustand in Q' und delta ' (q', a) = r' wird Übergang in delta '. 3. Wiederhole (2) bis keine neuen Zustände oder Übergänge mehr konstruiert werden können. 4. Endzustände: F' = {q' element Q' arrowvertex q' intersection F notequal emptyset } d. h. q' ist Endzustand, wenn seine Zustandsmenge einen Endzustand von A enthält. (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 711 Ziele: Konstruktionsprinzip verstehen in der Vorlesung: (Zusammen mit Mod-7.10 und 7.11a) * Erläuterungen zur Konstruktion, * Konstruktion am Beispiel, Dies ist ein Beispiel für ein wichtiges, induktives Konstruktionsschema: * Gegeben eine Regel und ein Anfangswert. * Wende die Regel an, solange sich noch etwas Neues ergibt. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.1 -------------------------------------------------------------------------------- Mod - 7.11a Beispiel zur Konstruktion NDEA -> DEA 2 nicht-deterministisch A Sprache: (a | b)* a (a | b) a Worte w über {a, b} mit |w| > 2 und a a drittletztes Zeichen ist ein a a 0 1 2 3 b b b a a a {0} {0,1} {0,1,2} {0,1,2,3} b a b b b b a {0,3} a b {0,2} {0,2,3} a b a deterministisch A' {0,1,3} b (c) 2012 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 711a Ziele: Konstruktionsprinzip am Beispiel verstehen in der Vorlesung: (Zusammen mit Mod-7.11) * Erläuterungen zur Konstruktion, * Konstruktion am Beispiel, nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.1 -------------------------------------------------------------------------------- Mod - 7.12 Endliche Automaten mit Ausgabe Man kann mit endlichen Automaten auch Reaktionen der modellierten Maschine spezifizieren: Automaten mit Ausgabe. Wir erweitern den Automaten um ein endliches Ausgabealphabet T und um eine Ausgabefunktion. Es gibt 2 Varianten für die Ausgabefunktion: Mealy-Automat: Moore-Automat: Eine Ausgabefunktion lambda : Q x Sigma -> T* Eine Ausgabefunktion mu : Q -> T* ordnet den Zustandsübergängen jeweils ordnet den Zuständen jeweils ein Wort über dem Ausgabealphabet zu. ein Wort über dem Ausgabealphabet zu. Es wird bei Erreichen des Zustands Graphische Notation: ausgegeben. T := {x, y} T := {x, y} 2 22 a / x a x 0 a / x 0 a b / y b 1 1 y Ein Mealy-Automat kann die Ausgabe feiner differenzieren als ein Moore-Automat. (c) 2012 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 712 Ziele: Zwei Ausgabevarianten in der Vorlesung: * Erläuterungen dazu; * Wenn keine Ausgabe angegeben ist, wird das leere Wort als Ausgabe angenommen. * Mealy- und Moore-Automaten werden auch so definiert, dass jeweils ein Zeichen statt ein Wort ausgegeben werden. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.1 -------------------------------------------------------------------------------- Mod-7.13 Beispiele für endliche Automaten mit Ausgabe Die Spezifikation des Getränkeautomaten aus Mod-7.2 wird mit Ausgabe versehen: Mealy-Automat Moore-Automat T = {1EUR, 2EUR, Getränk} 3 GetränkNehmen / Getränk Getränk GetränkNehmen KlappeÖffnen 2EUR 2 2EUR 2 0 1EUR 1EUR 0 1EUR 1EUR 1 1 GeldRück GeldRück GeldNehmen / 1EUR GeldRück 4 1EUR GeldRück / 2EUR 5 2EUR GeldNehmen (c) 2012 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 713 Ziele: Ausgabe zuordnen in der Vorlesung: Erläuterungen dazu * Mealy-Automat erläutern * An einigen Positionen bleibt die Ausgabe leer. * Moore-Automat erläutern * Zusätzliche Zustände begründen nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.1 -------------------------------------------------------------------------------- Mod - 7.14 Endlicher Automat zur Telefonbedienung on-hook on-hook Idle off hook on-hook Dial tone do: sound dial tone time-out Time-out time-out do: sound loud beep digit(n) on-hook digit(n) Dialing invalid number Recorded message Busy tone number busy valid number do: slow busy tone do: play message on-hook Connecting do: find connection Fast busy tone trunk busy routed do: fast busy tone Ringing message done on-hook do: ring bell called phone answers aus: on-hook / disconnect line / connect line Rumbaugh, Blaha, Connected Premerlani, Eddy, Lorensen: called phone hangs up Object-oriented on-hook / disconnect line Modeling and Design, Disconnected Prentice-Hall, 1991 (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 714 Ziele: Praktisches Modellierungsbeispiel sehen in der Vorlesung: * Erläuterungen dazu * Eingabe sind Ereignisse beim Telefonieren * Ausgabe sind ausgelöste Aktionen * Ausgabe ist sowohl einigen Zuständen (do:...) als auch einigen Übergängen (/...) zugeordnet. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.1 Übungsaufgaben: Modellieren Sie die Bedienung des Getränkeautomaten durch endliche Automaten. Modellieren Sie Das Betätigen der Tasten, die Geldeingabe, Geldrückgabe und Getränkeausgabe. -------------------------------------------------------------------------------- Mod - 7.14a Endliche Automaten in UML: Modell einer Uhr UML Diagrammtyp Statecharts: Bedienung einer Uhr Modellierung von Abläufen Einstellen von Zeit, Wecker, Stoppuhr Konzeptuelle Grundlage: sm Uhr-Einstellung Endliche Automaten Zeit Zustände können hierarchisch a zu Teilautomaten verfeinert b b werden. Stunde b Minute Mehrere Teilautomaten können + - + - "quasi-gleichzeitig" Übergänge ausführen - zur Modellierung von Nebenläufigkeit. x a a Anfangszustand x x Endzustand Stoppuhr Wecker a Stunde elementarer Zustand Teilautomat (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 714a Ziele: UML Statechart am Beispiel kennenlernen in der Vorlesung: Erläuterungen dazu * Wiederholtes Betätigen der Taste "a" schaltet zwischen der Einstellung von Zeit, Wecker und Stoppuhr um. * Taste "x" beendet das Einstellen. * Der Teilautomat "Zeit" ist weiter verfeinert: * Von jedem seiner 3 Zustände wird er mit "a" oder "x" verlassen. * Jedes Statechart kann systematisch in einen endlichen Automaten mit gleichem Verhalten transformiert werden. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.1.5 -------------------------------------------------------------------------------- Mod - 7.14b Modellierung von Nebenläufigkeit: Beginn eines Tennisspieles UML Statechart Det. endlicher Automat Aufruf S A B S B S A A B A B S B S A SpielLäuft SpielLäuft ... ... Mit dem "Aufruf" des werden die 3 Teilautomaten des mittleren Zustandes "gleichzeitig" aktiviert. Der gleichbedeutende endliche Automat modelliert alle Reihenfolgen Sie führen jeweils einen Übergang aus (Ankunft der Übergänge S, A, B. von Schiedsrichter, Spieler A, Spieler B). Das Statechart abstrahiert davon. Wenn sie ihre Endzustände erreicht haben, wird der zusammengesetzte Zustand verlassen. (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 714b Ziele: Modellierung von Nebenläufigkeit in der Vorlesung: Erläuterungen dazu * Es ist nicht relevant, in welcher Reihenfolge die Übergänge in den Teilautomaten des Statechart ausgeführt werden. * Deshalb ist das Statechart übersichtlicher als der endliche Automat. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.1.5 -------------------------------------------------------------------------------- Mod-7.15 7.2 Petri-Netze Petri-Netz (auch Stellen-/Transitions-Netz): Formaler Kalkül zur Modellierung von Abläufen mit nebenläufigen Prozessen und kausalen Beziehungen Basiert auf bipartiten gerichteten Graphen: * Knoten repräsentieren Bedingungen, Zustände bzw. Aktivitäten. * Kanten verbinden Aktivitäten mit ihren Vor- und Nachbedingungen. * Knotenmarkierung repräsentiert den veränderlichen Zustand des Systems. * graphische Notation. C. A. Petri hat sie 1962 eingeführt. Es gibt zahlreiche Varianten und Verfeinerungen von Petri-Netzen. Hier nur die Grundform. Anwendungen von Petri-Netzen zur Modellierung von * realen oder abstrakten Automaten und Maschinen * kommunizierenden Prozessen in der Realität oder in Rechnern * Verhalten von Hardware-Komponenten * Geschäftsabläufe * Spielpläne (c) 2012 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 715 Ziele: Einführung zu Petri-Netzen in der Vorlesung: Erläuterungen dazu nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.2 -------------------------------------------------------------------------------- Mod-7.16 Einführendes Beispiel Das Petri-Netz modelliert zwei zyklisch ablaufende Prozesse. Die mittlere Stelle synchronisiert die beiden Prozesse, so dass sie sich nicht zugleich in den Zuständen A und B befinden können. Prinzip: gegenseitiger Ausschluss durch Semaphor S A B (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 716 Ziele: Eindruck von Petri-Netzen in der Vorlesung: informelle Erläuterungen zu * parallelen Prozessen * gegenseitigem Ausschluss * Markierung und Schalten in Petri-Netzen nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.2 -------------------------------------------------------------------------------- Mod-7.17 Definition von Petri-Netzen Ein Petri-Netz ist ein Tripel P = (S, T, F) mit S Menge von Stellen, repräsentieren Bedingungen, Zustände; graphisch Kreise T Menge von Transitionen oder Übergänge, repräsentieren Aktivitäten; graphisch Rechtecke F Relation mit F reflexsubset S multiply T union T multiply S repräsentieren kausale oder zeitliche Vor-, Nachbedingungen von Aktivitäten aus T P bildet einen bipartiten, gerichteten Graphen mit den Knoten S union T und den Kanten F. Zu einer Transition t in einem Petri-Netz P sind folgende Stellenmengen definiert Vorbereich (t) := { s | (s, t) element F} 1 Nachbereich (t) := { s | (t, s) element F} 4 Der Zustand des Petri-Netzes wird durch eine 2 t Markierungsfunktion angegeben, die 5 jeder Stelle eine Anzahl von Marken zuordnet: MP: S arrowright Iota N0 3 Sind die Stellen von 1 bis n nummeriert, so kann man MP als Folge angeben, z. B. (1, 2, 1, 0, 1) Vorbereich Nachbereich (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 717 Ziele: Petri-Netz formal verstehen in der Vorlesung: Erläuterungen zu den Begriffen nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.2 Verständnisfragen: Welche Arten von Kanten kann es in einem Petri-Netz nicht geben? -------------------------------------------------------------------------------- Mod-7.18 Schaltregel für Petri-Netze Das Schalten einer Transition t überführt eine Markierung M in eine Markierung M`. Eine Transition t kann schalten, wenn für alle Stellen s element Vorbereich (t) gilt M(s) greaterequal 1. Wenn eine Transition t schaltet, gilt für die Nachfolgemarkierung M`: M`(v) = M(v) - 1 für alle vorher v element Vorbereich(t) \ Nachbereich(t) M`(n) = M(n) + 1 für alle n element Nachbereich(t) \ Vorbereich(t) t M`(s) = M(s) sonst Wenn in einem Schritt mehrere Transitionen schalten können, wird eine davon nicht-deterministisch ausgewählt. nachher In jedem Schritt schaltet genau eine Transition - auch wenn das Petri-Netz parallele Abläufe modelliert! t Zwei Transitionen mit gemeinsamen Stellen im Vorbereich können (bei passender Markierung) im Konflikt stehen: Jede kann schalten, aber nicht beide nacheinander. (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 718 Ziele: Schaltregel verstehen in der Vorlesung: * Schaltregel erläutern * nicht-deterministische Auswahl zeigen, * Konflikt zwischen mehreren Transitionen, die Schalten können zeigen. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.2 -------------------------------------------------------------------------------- Mod-7.19 Markierungen Zu jedem Petri-Netz wird eine Anfangsmarkierung M0 angeben. a c z. B. M0 = (1, 0, 1, 0, 1) 3 1 2 4 5 Wir sagen, eine Markierung M2 ist von einer Markierung M1 aus erreichbar, wenn es ausgehend von M1 eine Folge von Transitionen b d gibt, die nacheinander schalten und M1 in M2 überführen können. Die Markierungen eines Petri-Netzes kann man als gerichteten Markierungsgraphen darstellen: * Knoten: erreichbare Markierung * Kante x->y: Die Markierung x kann durch Schalten einer Transition in y übergehen. M (1, 0, 1, 0, 1) 0 a c Markierungsgraph b d (0, 1, 0, 0, 1) (1, 0, 0, 1, 0) (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 719 Ziele: Darstellung von Markierungen verstehen in der Vorlesung: Markierung als * Funktion, * Tupel, * Knoten im Markierungsgraph; * Zusammenhang zu endlichen Automaten. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.2 -------------------------------------------------------------------------------- Mod-7.20 Schaltfolgen Beispiel für eine Schaltfolge Schaltfolgen kann man angeben als zum Petri-Netz auf Mod-7.19: * Folge von Markierungen (1, 0, 1, 0, 1) a * Folge der geschalteten Transitionen (0, 1, 0, 0, 1) b (1, 0, 1, 0, 1) c (1, 0, 0, 1, 0) d (1, 0, 1, 0, 1) Schaltfolgen können als Wörter einer Sprache aufgefasst werden. 1 3 alle Schaltfolgen ohne Nachfolgemarkierung b haben die Form: an b cn a c 2 Petri-Netze können unbegrenzt zählen: Anzahl der Marken auf einer Stelle. (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 720 Ziele: Mit Schaltfolgen modellieren in der Vorlesung: * Notation von Schaltfolgen, * Zusammenhang zu Sprachen von endlichen Automaten. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.2 -------------------------------------------------------------------------------- Mod-7.21 Modellierung alternierender zyklischer Prozesse Beispiel: Einfache Modellierung einer Ampelkreuzung: Nord-Süd-Richtung Ost-West-Richtung * 2 sich zyklisch wiederholende Prozesse rot rot Wechselschalter * Die beiden Stellen "Wechselschalter" koppeln die Prozesse, sodass sie alternierend fortschreiten. grün_an grün_an * Alle Stellen repräsentieren Bedingungen: 1 oder 0 Marken * "Beobachtungsstelle" B modelliert, grün wieviele Richtungen "grün" haben grün B rot_an rot_an (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 721 Ziele: Modellieren von Bedingungen lernen in der Vorlesung: Erläuterung * der zyklischen Prozesse, * der Bedingungen, * der Rolle der Beobachtungsstelle. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.2 -------------------------------------------------------------------------------- Mod-7.22 Beispiel für ein binäres Netz Ein Petri-Netz heißt binär (sicher), wenn für alle aus M0 erreichbaren Markierungen M und für alle Stellen s gilt M(s) lessequal 1. Petri-Netze, deren Stellen Bedingungen repräsentieren müssen binär sein. Beispiel: Modellierung einer Sensor-gesteuerten Ampelkreuzung: Wunsch rot rot Wunsch Sensor grün grün Sensor frei grün grün frei wieviele grün? rot rot aus: B. Baumgarten: Petri-Netze, Bibliographisches Institut & F. A. Brockhaus AG, 1990 (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 722 Ziele: Stellen als Bedingungen verstehen in der Vorlesung: * Erläuterungen zu dem Beispiel, * Vor- und Nachbedingungen diskutieren, * Eigenschaften diese Modells diskutieren nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.2 -------------------------------------------------------------------------------- Mod - 7.23 Lebendige Petri-Netze Petri-Netze modellieren häufig Systeme, die nicht anhalten sollen. Ein Petri-Netz heißt schwach lebendig, wenn es zu jeder von M0 erreichbaren Markierung eine Nachfolgemarkierung gibt. Eine Transition t heißt lebendig, wenn es zu jeder von M0 erreichbaren Markierung M' eine Markierung M'' gibt, die von M' erreichbar ist, und in der t schalten kann. Ein Petri-Netz heißt lebendig, wenn alle seine Transitionen lebendig sind. Beispiel für ein lebendiges Petri-Netz (Mod-7.19): a c Markierungsgraph 3 1 2 4 5 M (1, 0, 1, 0, 1) 0 a c b d b d (0, 1, 0, 0, 1) (1, 0, 0, 1, 0) (c) 2012 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 723 Ziele: Begriffe zur Lebendigkeit von Netzen verstehen in der Vorlesung: Erläuterungen zu * nicht-terminierenden Systemen, * Lebendigkeitsbegriffen, am Beispiel von Mod-7.19 nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.2 -------------------------------------------------------------------------------- Mod - 7.23a Verklemmungen Verklemmung: Ein System kann unerwünscht anhalten, weil das Schalten einiger Transitionen zyklisch voneinander abhängt. Sei: sigma reflexsubset S eine Teilmenge der Stellen eines Petri-Netzes und Vorbereich (sigma ) := {t | es gibt s element sigma : (t, s) element F}, d. h. die Transitionen, die auf Stellen in sigma wirken Nachbereich (sigma ) := {t | es gibt s element sigma : (s, t) element F}, d. h. die Transitionen, die Stellen in sigma als Vorbedingung haben Dann ist sigma eine Verklemmung, wenn Vorbereich (sigma ) reflexsubset Nachbereich (sigma ). Wenn für alle s element sigma gilt M (s) = 0, dann kann es keine Marken auf Stellen in sigma in einer Nachfolgemarkierung von M geben. Vorbereich(sigma ) sigma Nachbereich(sigma ) sigma ist Verklemmung 1 2 3 c a 1 2 d a b c b 3 e Vorbereich(sigma ) reflexsubset Nachbereich(sigma ) (c) 2012 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 723a Ziele: Begriff Verklemmung verstehen in der Vorlesung: Erläuterungen zu * Verklemmungen am Beispiel von Mod-7.24 nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.2 -------------------------------------------------------------------------------- Mod - 7.24 Verklemmung beim Lesen von Dateien Datei 1 Datei 2 lesen Datei 1 Datei 2 lesen 1 2 a d Prozess 1 Prozess 2 3 6 s = {1, 2, 4, 5, 7, 8} 5 Datei 2 Datei 1 Vorbereich (s) 8 lesen lesen = {b, c, e, f} b e Nachbereich (s) 4 7 = {a, b, c, d, e, f} M (s) = 0 c f Anfangsmarkierung: Dateien Dateien freigeben freigeben (1, 1, 0, 0, 1, 0, 0, 1) (c) 2012 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 724 Ziele: Beispiel für eine Verklemmung in der Vorlesung: Erläuterung: * Jeder der Prozesse fordert nacheinander zwei Dateien an und gibt sie dann beide wieder frei. * Die Verklemmung tritt ein, wenn jeder Prozess eine Datei belegt und auf die andere wartet. * Sigma charakterisiert diese Situation. * Es gibt verschiedene Techniken, die Verklemmung zu vermeiden, z. B. * Bei einem Prozess die Reihenfolge der Dateien vertauschen. * Beide Dateien zugleich anfordern. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.2 -------------------------------------------------------------------------------- Mod - 7.25 Kapazitäten und Gewichte k=3 Man kann Stellen eine begrenzte Kapazität von k element Iota N Marken zuordnen. k=2 Die Bedingung, dass eine Transition t schalten kann, wird erweitert um: Die Kapazität keiner der Stellen im t Nachbereich von t darf überschritten werden. t kann nicht schalten Kanten kann ein Gewicht n element Iota N zugeordnet werden: sie bewegen beim Schalten n Marken. 2 3 Beispiel: Beschränkter Puffer Produzent Konsument 2 k=6 (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 725 Ziele: Konzepte verstehen in der Vorlesung: Erläuterung der beiden Konzepte am Beispiel. * Schaltregel wird ergänzt. * Produzent liefert immer 2 Einheiten zugleich (Kantengewicht 2). * Produzent kann nur liefern (schalten), wenn die Pufferstelle noch freie Kapazität. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.2 -------------------------------------------------------------------------------- Mod - 7.26 Beispiel: Leser-Schreiber-System n Leser-Prozesse und m Schreiber-Prozesse operieren auf derselben Datei. Mehrere Leser können zugleich lesen. Ein Schreiber darf nur dann schreiben, wenn kein anderer Leser oder Schreiber aktiv ist. Modellierung: ein Schreiber entzieht der Synchronisationsstelle alle n Marken. Datei lesen Datei schreiben warten warten n Leser- n Prozesse n m Schreiber- Prozesse schreiben lesen n n Datei Datei keine Aktivität freigeben freigeben keine Aktivität (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 726 Ziele: Beispiel für Kapazitäten und Gewichte in der Vorlesung: * Erläuterung des Leser-Schreiber-Systems. * Allerdings können wechselnde Leser die Schreiber auf Dauer blockieren. Das Petri-Netz ist nicht fair. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 7.2 Übungsaufgaben: Modellieren Sie die Bedienung des Getränkeautomaten durch Petri-Netze. Modellieren Sie Das Betätigen der Tasten, die Geldeingabe, Geldrückgabe und Getränkeausgabe. --------------------------------------------------------------------------------