Vorlesung 5

Question 1

Was beschreibt das synchrone Produkt (SYPC) in der Komposition von Prozessen?

Answer 1

Das synchrone Produkt (SYPC) ist ein Kompositionsoperator, der zwei Komponenten so verbindet, dass sie bei gemeinsamen Ereignissen synchronisiert werden. Private Ereignisse, die nur in einer der Komponenten auftreten, sind jedoch jederzeit möglich, ohne dass sie die andere Komponente beeinflussen.

Question 2

Was bedeutet partieller Gleichschritt im Kontext des SYPC-Operators?

Answer 2

Der partielle Gleichschritt im Kontext des SYPC-Operators bedeutet, dass die gekoppelten Komponenten nur bei gemeinsamen Ereignissen synchronisiert werden, während sie bei privaten Ereignissen unabhängig voneinander agieren können.

Question 3

Welche Zustände enthält ein komponiertes System G, das mit dem SYPC-Operator erstellt wurde?

Answer 3

Ein komponiertes System G, das mit dem SYPC-Operator erstellt wurde, enthält nur die Zustandsübergänge, die durch die Synchronisation von gemeinsamen Ereignissen erreichbar sind. Nicht erreichbare Zustände aufgrund von fehlender Synchronisation sind nicht enthalten.

Question 4

Answer 4

Question 5

Was passiert im Spezialfall des synchronen Produkts, wenn die beiden Systeme keine gemeinsamen Ereignisse haben?

Answer 5

Question 6

Was ist ein autonomes Petrinetz?

Answer 6

Question 7

Wie lässt sich die Struktur eines Petrinetzes beschreiben?

Answer 7

Question 8

Was sind Prästellen und Poststellen in einem Petrinetz?

Answer 8

Question 9

Wie wird der aktuelle Zustand eines Petrinetzes dargestellt?

Answer 9

Der aktuelle Zustand eines Petrinetzes wird durch eine Markierung der Stellen mit Marken festgelegt. Diese Markierung zeigt die Verteilung der Ressourcen oder Zustände in einem Netz zu einem bestimmten Zeitpunkt an.

Question 10

Was bedeutet es, dass ein Petrinetz reine Netze sind?

Answer 10

Reine Netze sind Petrinetze, die angenommen haben, dass keine Schlingen enthalten sind. Das bedeutet, dass keine Transition direkt mit sich selbst durch eine Stelle verbunden ist, was die Analyse und das Verständnis der Netzstruktur vereinfacht.

Question 11

Wie entsteht die Netzwerkdynamik in autonomen Petrinetzen?

Answer 11

Die Netzwerkdynamik in autonomen Petrinetzen entsteht durch die Bewegung der Marken von den Prästellen über die Transitionen zu den Poststellen, was auch als Schalten oder Feuern von Transitionen bezeichnet wird.

Question 12

Was ist die Schaltregel für autonome Petrinetze?

Answer 12

Eine Transition t ist aktiviert und kann schalten, wenn alle ihre Prästellen markiert sind und alle ihre Poststellen nicht markiert sind. Beim Schalten werden den Prästellen Marken entzogen und die Poststellen markiert.

Question 13

Kann die Anzahl der Marken in einem autonomen Petrinetz durch Schalten verändert werden?

Answer 13

Ja, die Anzahl der Marken im Netz kann sich durch das Schalten verändern, was darauf hinweist, dass das Verhalten des Netzes nicht deterministisch sein kann, insbesondere wenn mehrere Transitionen gleichzeitig aktiviert sind.

Question 14

Wie wird der aktuelle Zustand eines Petrinetzes dargestellt?

Answer 14

Der aktuelle Zustand eines Petrinetzes zu einem diskreten Zeitpunkt wird durch den Markierungsvektor
p(k)-> repräsentiert, dessen Elemente gleich Eins sind, wenn die entsprechende Stelle markiert ist, und sonst Null.

Question 15

Was beschreibt der Schaltvektor in einem autonomen Petrinetz?

Answer 15

Der Schaltvektor t(k)-> zeigt an, welche Transitionen zum aktuellen Zeitpunkt schalten. Jedes Element des Vektors ist gleich Eins, wenn die entsprechende Transition schaltet, ansonsten ist es Null.

Question 16

Wie lässt sich SPC kurz beschreiben?

Answer 16

nur gemeinsame Ereignisse finden synchron statt

Question 17

was ist davon der erreichbare und nicht erreichbare Teil?

Answer 17

Question 18

Was ist das Ergebnis der Anwendung von SPC auf dieses Beispiel?

Answer 18

Question 19

Was beschreibt SYPC?

Answer 19

Den partiellen Gleichschritt zweier gekoppelter Komponenten. Keine strenge Synchronisation, wie bei SPC.

Question 20

Was ist das Ergebnis der Anwendung von SPC auf dieses Beispiel?

Answer 20

Question 21

Was von diesem Beispiel der Anwendung von SYPC gehört zu SPC spezifisch und was nicht?

Answer 21

Question 22

Wann ist es etwas Ko-erreichbar?

Answer 22

Ko-Erreichbar, wenn ich
von einem aktuellen Zustand x aus einer Folge s in einen markierten Zustand komme

Question 23

Was liefert die Ac-Operation? Nimm Bezug auf die Zustände und die Sprachen L(g) und L_m(G)

Answer 23

Es antwortet mit einem G auf einen G, mit der Menge der erreichbaren Zustände bedingt durch die Folge s. Nicht erreichbare Zustände werden gestrichen. Diese Operation hat keinen Einfluss auf die Sprache L(G) und L_m(G)

Question 24

Was ist der Zweck der Erreichbarkeitsanalyse in der Analyse logischer DES?

Answer 24

Die Erreichbarkeitsanalyse dient dazu, zu bestimmen, welche System- oder Prozesszustände vom Anfangszustand aus erreichbar sind und ob ein System oder Prozess aus einem beliebigen Zustand heraus einen Zielzustand erreichen kann.

Question 25

Was versteht man unter Deadlock, Livelock und Blockierung in der Analyse von DES?

Answer 25

Deadlock, Livelock und Blockierung sind Begriffe, die beschreiben, ob ein System oder Prozess immer adäquat beendet werden kann. Ein Deadlock bezeichnet eine Situation, in der keine Fortsetzung möglich ist, ein Livelock eine endlose Schleife ohne Fortschritt und eine Blockierung ein Zustand, in dem bestimmte Aktionen nicht mehr durchführbar sind.

Question 26

Was ist die strukturelle Analyse und Invarianten in der Analyse von DES?

Answer 26

Strukturelle Analyse und Invarianten beziehen sich auf Methoden, um Analysefragen zu beantworten, die unabhängig von Parametereinstellungen wie dem Anfangszustand des Systems sind. Sie helfen zu verstehen, welche Eigenschaften des Systems unter allen Umständen erhalten bleiben.

Question 27

Welche Vorteile bietet die Verwendung formaler Beschreibungsformen in der Analyse von DES?

Answer 27

Formale Beschreibungsformen wie formale Sprachen, Automaten und Petrinetze ermöglichen eine präzise und analytische Untersuchung verschiedener Aspekte von DES. Sie bieten Werkzeuge, um komplexe Systemzustände und deren Dynamik zu modellieren und zu analysieren.

Question 28

Wie werden die Methoden der Erreichbarkeits- und Ko-Erreichbarkeitsanalyse, Deadlock/Livelock/Blockierung sowie strukturelle Analyse in Bezug auf DES angewendet?

Answer 28

Diese Methoden werden jeweils auf Generatoren und Petrinetze angewendet, um die dynamischen und strukturellen Eigenschaften von DES zu untersuchen. Sie ermöglichen es, die Machbarkeit von Prozessabläufen zu prüfen und potenzielle Probleme wie Deadlocks oder unerwünschte Endlosschleifen zu identifizieren.

Question 29

Was bedeutet es, dass ein Zustand in einem Generator erreichbar ist?

Answer 29

Ein Zustand ist in einem Generator erreichbar, wenn es eine Sequenz von Ereignissen in Σ ∗ gibt, die, wenn sie auf den Anfangszustand x 0 angewendet wird, zum Zustand x führt.

Question 30

Was ist die Ac-Operation in der Analyse von Generatoren?

Answer 30

Die Ac-Operation definiert eine reduzierte Form eines Generators, indem sie ihn auf seinen erreichbaren Teil beschränkt. Dies geschieht durch die Definition von X ac , der Menge der erreichbaren Zustände, und der Restriktion der Zustandsübergangsfunktion δ auf diese Menge.

Question 31

Wie wird die Erreichbarkeit eines Generators bestimmt?

Answer 31

Question 32

Answer 32

Question 33

Warum ist es ausreichend, die reduzierte Form eines Generators zu betrachten, um Erreichbarkeit zu prüfen?

Answer 33

Es ist ausreichend, die reduzierte Form eines Generators zu betrachten, weil die Erreichbarkeit eines Zustandes impliziert, dass alle Zustände, die in der reduzierten Form vorhanden sind, vom Anfangszustand aus erreicht werden können. Nicht erreichbare Zustände haben keinen Einfluss auf die Erreichbarkeit und das Verhalten des Generators.

Question 34

Was bedeutet Ko-Erreichbarkeit in Bezug auf Generatoren?

Answer 34

Question 35

Was ist die CoAc-Operation bei der Analyse von Generatoren?

Answer 35

Die CoAc-Operation definiert eine reduzierte Form eines Generators, die nur die ko-erreichbaren Zustände umfasst. Diese Operation hat im Allgemeinen Einfluss auf die Menge L(G) der von G erzeugten Strings, da durch ihre Anwendung auch erreichbare Zustände eliminiert werden können.

Question 36

Wie wird die Ko-Erreichbarkeit eines Generators bestimmt?

Answer 36

Ein Generator ist ko-erreichbar, wenn er gleich seiner durch die CoAc-Operation reduzierten Form ist, d.h., G=CoAc(G). Ist der Generator identisch mit seiner CoAc-Form, sind alle Zustände im Generator ko-erreichbar.

Question 37

Answer 37

Question 38

Was ist der Unterschied zwischen Erreichbarkeit und Ko-Erreichbarkeit in DES?

Answer 38

Während Erreichbarkeit sich darauf bezieht, dass ein Zustand vom Anfangszustand aus erreicht werden kann, impliziert Ko-Erreichbarkeit, dass der Zustand von jedem Zustand aus erreichbar ist. Die CoAc-Operation hilft, die Ko-Erreichbarkeit zu analysieren, indem sie den Generator auf Zustände reduziert, die von jedem anderen Zustand aus erreichbar sind.

Question 39

Wann ist ein Generator ko-erreichbar?

Answer 39

Question 40

Wie kann Ko-Erreichbarkeit sprachentheoretisch dargestellt werden?

Answer 40

Question 41

Was bewirkt die Anwendung von CoAc und Ac Operationen nacheinander auf einen Generator?

Answer 41

Die sequenzielle Anwendung von CoAc und Ac Operationen auf einen Generator führt zu einem Generator, der weder nicht erreichbare noch nicht ko-erreichbare Zustände besitzt. Dieser Prozess wird als Trimmen des Generators bezeichnet.

Question 42

Was ist die Trim-Operation in der Analyse von DES?

Answer 42

Question 43

Wann gilt ein Generator G als 'Trim'?

Answer 43

Question 44

Was bedeutet das Ergebnis von Trim?

Answer 44

dass das Ergebnis weder nicht noch ko-erreichbar ist

Question 45

Was ist die Präfix Hülle?

Answer 45

Die Sprache der eigenen Elemente

Question 46

Answer 46

Question 47

Was ist ein Deadlock in der Analyse von Generatoren?

Answer 47

Question 48

Answer 48

Question 49

Was ist ein Livelock in der Analyse von Generatoren?

Answer 49

Ein Livelock ist ein Zustand oder eine Zustandsmenge in einem Generator G, von dem aus das System zwar Ereignisse generieren kann, die aber nie zu einem markierten Zustand führen. Bei einem Livelock bleibt das System in einer Schleife von Zuständen gefangen, ohne einen Fortschritt zu machen.

Question 50

Answer 50

Question 51

Was haben Deadlock und Livelock gemeinsam?

Answer 51

Sowohl Deadlock als auch Livelock verhindern, dass der Generator einen markierten Zustand erreicht. Im Falle eines Deadlocks kann der Generator keine weiteren Zustände erreichen, während bei einem Livelock das System aktiv bleibt, aber keinen nützlichen Fortschritt erzielt.

Question 52

Was bedeutet Blockierung in DES?

Answer 52

Blockierung bedeutet, dass der Generator aufgrund eines Deadlocks oder Livelocks in einem Zustand gefangen ist, in dem ein markierter Zustand, der einen fertigen Auftrag darstellt, nicht erreicht werden kann.

Question 53

Was besagt die Definition von Nichtblockierung in Bezug auf DES?

Answer 53

Question 54

Was sind stark zusammenhängende Zustände in DES?

Answer 54

Question 55

Was definiert eine stark zusammenhängende Zustandsmenge in DES?

Answer 55

Question 56

Wie wird die Eigenschaft "stark zusammenhängend" in Bezug auf Zustandspaare und Zustandsmengen verstanden?

Answer 56

Question 57

Wie wird ein Livelock in einem DES identifiziert?

Answer 57

Question 58

Unter welchen Bedingungen kann ein Deadlock in einem DES vorhanden sein?

Answer 58

Ein Generator G kann einen Deadlock enthalten, wenn die Menge der stark zusammenhängenden Zustände ∣X∣ genau eins beträgt.

Question 59

Wie erfolgt die Erreichbarkeitsanalyse bei Petrinetzen?

Answer 59

Die Erreichbarkeitsanalyse erfolgt bei Petrinetzen mit Hilfe des Erreichbarkeitsgrafen

Question 60

Wie erfolgt die Erstellung des Erreichbarkeitsgrafen?

Answer 60

1) Anfangszustand = Initialmarkierung 2) Bestimme die Menge aller aktivierten Transitionen 3) Bestimme alle Nachfolgemarkierungen 4) Erweitere Erreichbarkeitsgraf um entsprechende neue Knoten 5) Benenne die Kanten entsprechend der geschalteten Transitionen

Question 61

Wie erfolgt die Analyse des Erreichbarkeitsgrafen?

Answer 61

▪ Existieren im Erreichbarkeitsgrafen Blattknoten (Knoten ohne abgehende Kanten) existiert ein Deadlock. ▪ Existieren keine Blattknoten im Erreichbarkeitsgrafen, so ist Petrinetz schwach lebendig. ▪ Ist Erreichbarkeitsgraf stark zusammenhängend und kommt jede Transition an mindestens einer Kante des Erreichbarkeitsgrafen vor, ist das Petrinetz lebendig.

Question 62

Was versteht man unter Invarianten in Petrinetzen?

Answer 62

Invarianten sind Eigenschaften eines Petrinetzes, die unabhängig von der Anfangsmarkierung konstant bleiben und sich aus der Netztopologie ergeben. Sie werden durch die Analyse des Netzes ohne die Erstellung eines Erreichbarkeitsgraphen bestimmt.

Question 63

Welche Arten von Invarianten gibt es in Petrinetzen und was beschreiben sie?

Answer 63

Es gibt zwei Arten von Invarianten: - Transitionsinvarianten (T-Invarianten): Mengen von Transitionen, die beim Schalten die Markierung des Netzes reproduzieren und somit die Erreichbarkeit bestimmter Zustände ermöglichen. - Stelleninvarianten (S-Invarianten): Mengen von Stellen, bei denen der gewichtete Markenzahlvektor durch das Schalten von Transitionen konstant bleibt, was die Erhaltung bestimmter Ressourcen oder Bedingungen anzeigt.

Question 64

Gib eine typische analytische Netzbeschreibung an

Answer 64

Question 65

Was ist eine T-Invariante in Petrinetzen?

Answer 65

Eine T-Invariante ist eine ganzzahlige, elementare Lösung des linearen Gleichungssystems, das die Netzmatrix N und einen Transitionsvektor T(k) verwendet, um die unveränderte Markierung eines Netzes zu beschreiben, nachdem alle Transitionen in T(k) geschaltet haben.

Question 66

Was impliziert das Vorhandensein einer T-Invariante in einem Petrinetz?

Answer 66

Das Vorhandensein einer T-Invariante deutet darauf hin, dass das Netz in der Lage ist, zu einer bestimmten Markierung zurückzukehren, nachdem eine bestimmte Sequenz von Transitionen geschaltet hat. Es bedeutet jedoch nicht, dass jede Anfangsmarkierung reproduziert werden kann.

Question 67

Wie viele T-Invarianten existieren in einem Petrinetz?

Answer 67

Wenn die Netzmatrix N eines Petrinetzes die Dimension n x m hat und der Rang von N gleich r ist, dann gibt es genau m-r T-Invarianten.

Question 68

Welche Bedeutung haben T-Invarianten für die Analyse von Petrinetzen?

Answer 68

T-Invarianten helfen dabei, zyklische Verhaltensweisen im Netz zu identifizieren und zu verstehen, welche Transitionen in einem Zyklus involviert sind, der die Markierung unverändert lässt.

Question 69

Was versteht man unter einer S-Invariante in Petrinetzen?

Answer 69

Eine S-Invariante ist eine ganzzahlige, nichttriviale und nichtnegative Lösung des linearen Gleichungssystems, das die Netzmatrix � N eines Petrinetzes verwendet, um Bedingungen zu identifizieren, unter denen die gewichtete Summe der Marken konstant bleibt, unabhängig davon, welche Transitionen schalten.

Question 70

Was impliziert das Vorhandensein einer S-Invariante in einem Petrinetz?

Answer 70

Das Vorhandensein einer S-Invariante zeigt, dass es eine feste Gewichtung der Stellen gibt, bei der die Gesamtzahl der Marken im Netz während der Ausführung des Netzes konstant bleibt. Dies hilft dabei, Erhaltungsgesetze oder balancierte Flüsse im Netzwerk zu identifizieren.

Question 71

Wie viele S-Invarianten existieren in einem Petrinetz?

Answer 71

Wenn die Netzmatrix � N eines Petrinetzes die Dimension n x m hat und der Rang von � N gleich r ist, dann gibt es genau n-r S-Invarianten.