Minimierung von DFAs < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 20:09 Di 22.11.2011 | | Autor: | Dym |
| Aufgabe | Sei M = [mm] (Z,\summe,\delta,q_{0},E) [/mm] ein DFA und sei
[mm] D_{i}=\begin{cases}\{ \{ p,q \} | q \in E, p \not\in E\}, & i = 0
\\ D_{i-1} \cup \{\{p,q\} | \exists a \in \summe : \{\delta(p,a),\delta(q,a)\} \in D_{i-1} \}, & i > 0 \end{cases}
[/mm]
eine Folge zur Minimierung von M.
1. Zeigen Sie,dass [mm] D_{j} [/mm] = [mm] D_{j+1} [/mm] die Gleichheit [mm] D_{j} [/mm] = {{p,q} [mm] \subseteq [/mm] Z | q [mm] \not\sim [/mm] p } impliziert. |
Ich habe wirklich keine Ahnung wie ich die Aufgabe angehen soll, ich bitte hier nicht um eine Musterlösung, könnt ihr mir bitte eine Art Ansatz oder "Anfang" geben was ich tun muss bzw. wie ich bei dieser Aufgabe vorgehe? Bitte um Hilfe.
Gruß AJ
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Do 24.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:37 Mo 12.12.2011 | | Autor: | Gedro |
Ich weiss nicht, ob du noch Hilfe brauchst, aber ich poste mal meine Gedanken dazu. ^^
Du musst hier eine Implikation zeigen, d.h.
[mm] (D_{j} [/mm] = [mm] D_{j+1})\Rightarrow (D_{j} [/mm] = [mm] \{\{p,q\} \subseteq Z | q \not\sim p \})
[/mm]
Ich würde erstmal den Fall j=0 betrachten und die Implikation zeigen und daraufhin den Fall j>0 betrachten. Ich vermute du kannst dich hier recht gut an den Definitionen für diese Folge entlanghangeln, um die einzelnen Fälle zu zeigen.
MfG
Gedro
|
|
|
|
