DEA Minimieren?

Bild zum Beitrag

Ich verstehe diese Minimierung vom DEA nicht. Wieso werden die Paare (z2, z3), (z2,z4), (z3, z4) nicht gestrichen obwohl sie auf einen bereits gestrichenes Paar verweisen. Stattdessen werden sie am Ende zu dem Paar z234 zusammengefasst.

Die Aufgabe ist von hier:

https://studyflix.de/informatik/dea-minimieren-1212

1 Antwort

Vom Fragesteller als hilfreich ausgezeichnet

Jangler13

15.06.2023, 12:47

Eigentlich ist das Ziel bei dem Algorithmus alle Paare zu markieren, die nicht äquivalent sind.

Die Diagonale darf hier also nicht markiert werden, da jeder Zustand immer äquivalent zu sich selbst ist.

Die Vorangehensweise geht eigentlich so:

1. Starte mit einer Leeren Tabelle.

2. Markiere jedes paar, wo ein Zustand akzeptierend ist und der andere nicht. (Denn diese Zustände können nicht äquivalent sein)

3. Iteriere nun durch jedes nicht markierte Paar. Schaue dann, auf welche Paare dieses Paar abgebildet werden können. Wenn mindestens eines dieser Paare markiert ist, wird das betrachtete Paar markiert (denn das Paar kann nicht äquivalent sein)

4. Wiederhole schritt 3 (eine Wiederholung = alle unmarkierten Paare betrachten), bis kein neues Paar markiert wird)

Die nicht markierten Paare sind dann äquivalent.

Zur einfachheit reicht es aus, wenn du nur die Einträge unterhalb der Diagonale betrachtest. Denn:

1. Die Diagonale ist immer nicht markiert

2. Äquivalenz ist eine symmetrische Relation, weswegen die Relationsmatrix am Ende symmetrisch sein wird.

Es ist aber einfach nur falsch, die Einträge auf der Diagonalen und über der Diagonalen zu markieren.

Woher ich das weiß:Studium / Ausbildung – Mache derzeit meinen Mathematik Master

user941234

Fragesteller

15.06.2023, 12:55

Okay danke ich habs fast verstanden. Aber was meinst du mit "Markiere jedes paar, wo ein Zustand akzeptierend ist und der andere nicht?"

Jangler13

15.06.2023, 13:23

@user941234

Nehmen wir mal die Tabelle aus dem Bild, wie sie gerade ist.

(Die einträge in der Diagonalen sind aber nicht markiert, und das was über der Diagonalen ist, streichen wir)

Betrachte nun das Paar (Z_5, Z_0).

Wir betrachten nun jedes Paar welches von dem Paar erreicht werden kann (in diesem Fall schauen wir uns an, welches paar wir bekommen, wenn wir bei beiden Zuständen Richtung 0, oder bei beiden Zuständen Richtung 1 gehen)

Wir erhalten dann die beiden Paare

(Z_1, Z_5) sowie (Z_2, Z5)

Das Zweite paar ist markiert (bzw das Paar (Z_5, Z_2) ist markiert, aber wegen Symmetrie ist die Reihenfolge egal). Somit musst du das Paar (Z_5, Z_0) markieren.

Wenn du stattdessen dass paar (Z_2, Z_3) betrachtest wirst du sehen, dass die Paare (Z_4, Z_4) und (Z_5,Z_5) erreicht werden. Beide Paare sind nicht markiert, weswegen du das Paar (Z_2,Z_3) nicht markierst.

Ist das verständlicher?

user941234

Fragesteller

15.06.2023, 13:31

@Jangler13

Super gut erklaert. Habs verstanden. Danke!

Ähnliche Fragen

Minimierung eines DEA?

Wie kann ich diesen Automaten minimieren? Ich habe die Tabelle mit dem "Dreieck" gemacht und habe keine Minimierung entdeckt, wegen x0 und x1 Äquivalenz. Die Aufgabe lässt aber Schluss folgern, dass man in doch minimieren kann.

...zur Frage

Ein getriebe hat folgende zahnräder z1 30 Zähne, z2 10 zähne , z3 20zähne und z4 (Abtriebsrad)30Zähne.bestimme die drehrichtung und das Übersetzungsverhältni?

...zur Frage

DEA der Binärdarstellung aller Zahlen i akzeptiert, wenn diese durch 5 teilbar sind

Hallo Community,

wie ihr im Betreff schon sehen könnt komme ich bei einer Aufgabe nicht weiter. Ich soll einen DEA/DFA (Deterministischer Endlicher Automat) konstruieren, der die Binärdarstellung aller Zahlen "i" akzeptiert, wenn diese durch 5 teilbar sind (i%5=0). Eingabezeichen = binäres Alphabet.

Könnt ihr mit helfen?

...zur Frage

Reguläre Sprache Theoretische Informatik?

Wahr oder Falsch: Sei Σ = {0, 1} und sei L ⊆ Σ∗ regulär. Sei L′ die Sprache, die man aus L erhält, indem man in jedem Wort aus L jedes zweite Vorkommen von 0 durch 10, und jedes dritte Vorkommen von 1 durch 01 ersetzt. Dann ist L′ regulär. Begründen Sie Ihre Antwort.

...zur Frage

Was ist hier das Alphabet und syntaktischen Variablen?

...zur Frage

wie berechnet man die zahnräder z1 und z2?

Es ist ein 2 Stufen Getriebe gegeben ist z3= 17, z4=39, nan= 1425 1/min, nab=125 1/min, a=120 mm , m=3 danke im voraus

...zur Frage

Informatik DEA?

Hallo, ich hänge an der Aufgabe 9, ich weiß nicht wie ich weiter kommen soll. Hat jemand eine Idee oder einen Lösungsvorschlag?

danke im Voraus!

...zur Frage

Excel Vba mehrere Zufallszahlen, jedoch keine Wiederholungen?

Hallo,

Ich brauche 10 Variabeln, die einer Zufallszahl zugewiesen sind, jedoch dürfen sich die Zufallszahlen nicht wiederholen. Also z.B.

Z1= 23

Z2= 25

Z3= 25

Z4= 19

Z6= 17

....

Die "25" kommt nun 2 mal vor und das sollte nicht sein, also müsste Z2 oder Z3 zu einer anderen Zahl geändert werden.

Wie kann man das überprüfen lassen? Gibt es eine einfache und schnelle Möglichkeit ohne viel Code? Oder müsste man jede einzelne Variable mit if überprüfen?

MfG Fabian

...zur Frage

Was will die Aufgabe von mir (Informatik, Automaten)?

Was für ne Sprache soll man denn da angeben? Einfach alle Möglichkeiten aufschreiben, die zum Endzustand führen?

...zur Frage

DEA oder NEA (Automat)?

Ich wollte mal eure meine dazu wissen, ob dieser endliche Automat deterministisch ist oder nichtdeterministisch ist?

Meiner Meinung nach ist dieser Automat nichtdeterministisch, weil es kein eindeutigen Startzustand gibt, da man mit b oder c das Wort anfangen kann.

...zur Frage

Position im dreidimensionalen Raum zu einem bestimmten Zeitpunkt berechnen?

Hallo. Ich habe eine theoretische Frage.

Gehen wir davon aus, ich habe eine Objekt im Gravitationsfreien und Luftleeren Raum. Ich messe nun die Position dieses Objektes und erhalte die Koordinaten (X, Y, Z).

0.1 Sekunde später messe ich die Position wieder und erhalte (X1, Y1, Z1).

Noch einmal 0.1 Sekunden später messe ich die Position wieder und erhalte (X2, Y2, Z2).

Ich gehe davon aus, dass das Objekt sein Flugbahn beibehält.

Wie kann ich die Koordinaten des Objektes a Sekunden später berechnen?

Noch einmal zum Verständnis zusammengefasst:

Pos1 = (X, Y, Z); t = 0
Pos2 = (X1, Y1, Z1); t = 0.1
Pos3=(X2, Y2, Z2); t = 0.2
? PosX=(X3,Y3,Z3); t=a

Wie berechne ich PosX wenn a gegeben ist. (Bspw 0.5)

Vielen Dank :)

...zur Frage

Informatik Komplexe Zahlen in kartesischer Darstellung?

Hallo, ich studiere Informatik und wir haben das Thema Komplexe Zahlen. Wir sollen komplexe Zahlen in kartesischer Darstellung darstellen. Ich bräuchte eure Hilfe. Es wäre sehr nett, wenn ihr mir die folgenden Aufgaben erklären könntet mit Lösungsweg.

z1 = 3 + 4i

z2 = −2 + 3i

z3 = 5 − i

z4 = 6i

c) 3z1 − 4z2

d) 5z3 + 4z4

h) ich kann das hier nicht genau darstellen aber es ist ein zhoch3 und unter der hoch 3 ist noch eine 3

i) |z2| Andere frage noch: Wofür stehen diese | hier?

Lösungen:

c) 3z1 − 4z2 = 17

d) 5z3 + 4z4 = −10 + 39i

h) z 3 3 = 110 − 74i

i) |z2|

...zur Frage

Deterministischer endlicher Automat aus regulärem Ausdruck?

Guten Abend,

ich bin bei meiner Klausurvorbereitung auf folgende Aufgabe gestoßen:

Gegeben ist die Sprache 𝐿, die durch den regulären Ausdruck 𝑝(𝑖|𝑎) (𝑝(𝑖|𝑎))∗𝑝𝑜 erzeugt wird.

Geben Sie den Übergangsgraphen eines deterministischen endlichen Automaten (DEA) an, der die Sprache 𝐿 akzeptiert.

Dafür habe ich folgendes entworfen.

Meine Frage ist nun, was ich an den roten Fragezeichen hinschreiben kann. Es kann kein p sein, da es kein DEA mehr wäre. Wie würdet ihr es lösen?

Danke

...zur Frage

Wie kann ich verhindern, dass bei meinem Batch spiel steht echo ist ausgeschaltet off?

Script:

@echo off title Tic Tac Toe color 0F

:gebenick1 color0f echo. cls echo. echo. echo ###### ## ### ###### ## ### ###### #### ###### echo ## ## ## ## #### ## ## ## ## #### echo ## ## ## ## ## ## ## ## ## ## ## echo ## ## ### ## ## ## ### ## #### ###### echo. echo
echo. echo. echo Name des 1.Spieler: echo. set /p nick1="" goto bubu1 :lol1 color0f cls echo. echo. echo. echo. echo #################### echo Willkommen %nick1% echo #################### ping /n 2 localhost >NUL goto gebenick2

:gebenick2 color0f cls echo. echo. echo ###### ## ### ###### ## ### ###### #### ###### echo ## ## ## ## #### ## ## ## ## #### echo ## ## ## ## ## ## ## ## ## ## ## echo ## ## ### ## ## ## ### ## #### ###### echo. echo
echo. echo. echo Name des 2.Spieler: echo. set /p nick2="" goto bubu2 :lol2 color0f cls echo. echo. echo. echo. echo. echo. echo #################### echo Willkommen %nick2% echo #################### ping /n 2 localhost >NUL goto main

:main color0f

set z1=1 set z2=2 set z3=3 set z4=4 set z5=5 set z6=6 set z7=7 set z8=8 set z9=9

:Spieler1 cls

color 0f

echo. echo
echo
echo. echo %nick1% hat die 0 echo. echo. echo %z1%___%z2%___%z3% echo.
echo %z4%___%z5%___%z6% echo.
echo %z7%___%z8%___%z9% echo. echo. echo. set /p Zahl=%nick1% setzte eine Zahl: if %Zahl%==1 goto 1 if %Zahl%==2 goto 2 if %Zahl%==3 goto 3 if %Zahl%==4 goto 4 if %Zahl%==5 goto 5 if %Zahl%==6 goto 6 if %Zahl%==7 goto 7 if %Zahl%==8 goto 8 if %zahl%==9 goto 9

:1 if %z1%==x goto B if %z1%==0 goto A set z1=0 goto check

:2 if %z2%==x goto B if %z2%==0 goto A set z2=0 goto check

:3 if %z3%==x goto B if %z3%==0 goto A set z3=0 goto check

:4 if %z4%==x goto B if %z4%==0 goto A set z4=0 goto check

:5 if %z5%==x goto B if %z4%==0 goto A set z5=0 goto check

:6 if %z6%==x goto B if %z6%==0 goto A set z6=0 goto check

:7 if %z7%==x goto B if %z7%==0 goto A set z7=0 goto check

:8 if %z8%==x goto B if %z8%==0 goto A set z8=0 goto check

:9 if %z9%==x goto B if %z9%==0 goto A set z9=0 goto check

:Spieler2 cls echo. echo Hier wird gespielt: echo ####################### echo. echo %nick2% hat x echo. echo. echo %z1%___%z2%___%z3% echo. echo %z4%___%z5%___%z6% echo.
echo %z7%___%z8%___%z9% e

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen