Seiten

  • Startseite
  • Impressum
  • Inhalt
  • MINT
  • Sprache
  • Soziales
  • Geist
  • Kunst
  • Gemischtes
  • Gedichte

Freitag, 24. Juli 2015

DEA ≟ Petri-Netz


Deutsch

Die Antwort vorneweg: Nein, die Klasse der Petri-Net­ze ist mächti­ger als die der de­termi­nisti­schen endli­chen Automa­ten (DEA). Wären die bei­den Klas­sen äquivalent, dann gälte sowohl DEA ⊆ Petri-Netz als auch DEA ⊇ Petri-Netz; tatsächl­ich gilt aber nur Ers­te­res. D. h., dass man jeden DEA in ein Petri-Netz umwandeln kann, aber nicht umgekehrt. Beweis:
: Sei M = (Z, Σ, δ, z0, F) ein DEA mit der Zu­standsmenge Z, dem Alphabet Σ, der Übergangsfunkti­on δ, dem Startzu­stand z0 und der Endzu­standsmenge F. Damit P = (S, T, A, E, M) das ent­spre­chen­de Petri-Netz ist, set­zen wir hier die Stel­lenmenge S = Z, die Transitionenmenge T = Σ, die Stel­len­ausgangskan­tenmenge A = {δ-1(z) | z ∈ Z}, die Stel­len­ein­gangskan­tenmenge E = {(σ, δ(z, σ)) | σ ∈ Σ, z ∈ Z} und die Start­markierung M mit M(z0) = 1 und M(Z \ {z0}) = {0}.
: Es reicht, ein Gegenbei­spiel anzuge­ben. Das Petri-Netz P = (S, T, A, E, M) mit S = {s0, s1, s2}, T = {a(1), a(2), b(1), b(2)}, A = {(s0, a(1)), (s0, a(2)), (s1, b(1)), (s2, b(2))}, E = {(a(0), s2), (a(1), s0), (a(1), s1), (b(1), s2)} und (M(s0), M(s1), M(s2)) = (1, 0, 0) erkennt die Spra­che L = {anbn | n ≥ 1} Die­se Spra­che ist nicht regulär und kann somit nicht von ei­nem DEA erkannt wer­den.
Q. e. d.
Verweise:
R. Schertle: Struktur und Semantik von Petri-Netzen, 2006, Universität Stuttgart
M. Rücker: Petrinetze in der Schule, 2014, Humboldt-Universität zu Berlin

Keine Kommentare:

Kommentar veröffentlichen