Prüfung Frühjahr '05: Aufgabe 2.1

iphpbb - Forenarchiv: Archivbeitrag des Forums Studenten-Board

Verfügbare Informationen zu "Prüfung Frühjahr '05: Aufgabe 2.1"

Qualität des Beitrags:
Beteiligte Poster: MasterStyleGuide
Forum: Studenten-Board
Forenbeschreibung: "Informatik / Softwaretechnik - Uni Stuttgart"
aus dem Unterforum: Theoretische Informatik I
Antworten: 1
Forum gestartet am: Mittwoch 27.09.2006
Sprache: deutsch
Link zum Originaltopic: Prüfung Frühjahr '05: Aufgabe 2.1
Letzte Antwort: vor 1 Jahr, 4 Tagen, 16 Stunden, 43 Minuten

Alle Beiträge und Antworten

MasterStyleGuide - 03.10.2007, 11:50
Prüfung Frühjahr '05: Aufgabe 2.1
Aufgabe: (6 Punkte)
Minimieren Sie den folgenden DFA M mit dem bekannten Algorithmus. Zeichnen Sie den entstehenden minimalen Automaten und begrüunden Sie jeden Ihrer Schritte.

M = ({q0, q1, q2, q3, q4, q5, q6}, {a, b}, delta, {q1, q2, q4, q5, q6})
delta:
_.|_q0_|_q1_|_q2_|_q3_|_q4_|_q5_|_q6_|
a.|_q1_|_q3_|_q5_|_q3_|_q5_|_q3_|_q5_|
b.|_q0_|_q2_|_q4_|_q1_|_q4_|_q4_|_q2_|

Lösung:
Im ersten Schritt können folgende Paare markiert werden:
(q0, q1); (q0, q2); (q0, q4); (q0, q5); (q0;q6);
(q1, q3);
(q2, q3);
(q3, q4); (q3, q5); (q3, q6);

Im Zweiten Schritt können folgende Paare markiert werden:
(q0, q3);
(q1, q2); (q1, q4); (q1, q6);
(q2, q5);
(q4, q5);
(q5, q6);

Ab dann lässt sicht nichts mehr markieren.
Damit können folgende Zustände zusammengefasst werden:
(q1, q5);
(q2, q4, q6);

Und der minimalautomat sieht wie folgt aus:
M' = ({q0, q1q5, q3, q2q4q6}, {a, b}, delta', {q1q5, q2q4q6})
delta'
_.|___q0___|__q1q5__|___q3___|_q2q4q6_|
a.|__q1q5__|___q3___|___q3___|__q1q5__|
b.|___q0___|_q2q4q6_|__q1q5__|_q2q4q6_|

Mit folgendem Code, können Sie den Beitrag ganz bequem auf ihrer Homepage verlinken