Zustandsdiagramm endl. Automat < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Ein endlicher Automat soll die folgende Wortmenge akzeptieren:
[mm]\left \{ \left \{ a \left \{ a,c,t \right \}^l g \left \{ a,g,c \right \}^m t \right \}^n | l,m \geq 0,n \geq 1 \right \}[/mm]
Bsp.: agt, agtagt, acgt, aagt, …
Die EIngabe besteht aus den Worten des Alphabets [mm]\mathcal{A} = \left \{ a,c,g,t \right \}[/mm].
Zeichnen Sie für die definierte Wortmenge ein Zustandsübergangsdiagramm eines endlichen Automaten, der die Worte dieser Menge akzeptiert. F+gen Sie in Ihr Diagramm alle möglichen Übergänge und Fehlerzustände ein und machen Sie unnötige Verbindungen und Zustände kenntlich. |
Hallo zusammen,
ich wäre Euch sehr dankbar, wenn Ihr Euch meine Lösung zu dieser Aufgabe einmal anschauen und mir Feedback geben würdet: Ist die Lösung korrekt, gibt es Optimierungsmöglichkeiten?
Insgesamt habe ich aufgrund der immensen Komplexität meines Zustandsdiagrammes schon fast die Befürchtung, dass da etwas nicht passt.
Die Fehlerzustände (= "unnötige Verbindungen und Zustände") habe ich mit gestrichelten Linien eingezeichnet. Die farbliche Hervorhebung soll nur ein bisschen mehr Struktur in das Diagramm reinbringen.
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
Hallo Apfelchips,
>Ist die Lösung korrekt
gehört Deiner Meinung nach beispielsweise das Wort
attgat
zur Wortmenge [mm]\left \{ \left \{ a \left \{ a,c,t \right \}^l g \left \{ a,g,c \right \}^m t \right \}^n | l,m \geq 0,n \geq 1 \right \}[/mm] ? Und wenn ja, akzeptiert dieses Dein Automat?
Gruß
Anna
|
|
|
| |
|
Hallo Anna,
danke für Deine Hilfe.
> gehört Deiner Meinung nach beispielsweise das Wort
> attgat
> zur Wortmenge [mm]\left \{ \left \{ a \left \{ a,c,t \right \}^l g \left \{ a,g,c \right \}^m t \right \}^n | l,m \geq 0,n \geq 1 \right \}[/mm]
> ? Und wenn ja, akzeptiert dieses Dein Automat?
Ja, attgat gehört zur Wortmenge – und nein, mein Automat akzeptiert das nicht. Das macht aber leider alles noch unübersichtlicher.
Ich hab das Diagramm nochmals überarbeitet. Stimmt das so?
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:05 Sa 10.11.2012 | | Autor: | Anna-Lyse |
Hallo Patrick,
bevor ich mir Deine komplexe Zeichnung anschaue - Du hast ja z.B. bei 2 das a wieder auf Zustand 2 geführt .... Ihr dürft doch sicher auch mehrere Kanten zeichnen, die zum selben Folgezustand führen (i.A. dann nur einmal gezeichnet und mehrfach, durch Komma getrennt, beschriftet). Das würde das hier sicherlich noch etwas weniger komplex machen....
Gruß
Anna
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:09 Sa 10.11.2012 | | Autor: | Apfelchips |
Hallo Anna,
was meinst Du mit "mehrere Kanten, die zum selben Folgezustand führen"?
Eine mehrfach beschriftete Kante habe ich ganz unten beim Fehlerzustand (von Zustand 9 auf 10).
An anderen Stellen macht so etwas doch aber keinen Sinn, oder?
Sorry, ich werde daraus nicht ganz schlau.
|
|
|
| |
|
Hallo Patrick,
hatte leider doch noch nicht viel Zeit, aber IMHO scheint der jetzt so die richtigen Worte zu akzeptieren.
> was meinst Du mit "mehrere Kanten, die zum selben Folgezustand führen"?
>
> Eine mehrfach beschriftete Kante habe ich ganz unten beim Fehlerzustand (von Zustand 9 auf 10).
>
> An anderen Stellen macht so etwas doch aber keinen Sinn, oder?
Warum macht das keinen Sinn? Inwiefern?
Warum nicht z.B. bei 1 eine Kante, die wieder direkt zurück zu 1 führt mit a,c,t
anstatt 3 weitere Zustände?
Gruß
Anna
|
|
|
| |
|
Hallo Anna,
danke, dass Du Dir das nochmals angeschaut hast.
> > An anderen Stellen macht so etwas doch aber keinen Sinn,
> oder?
>
> Warum macht das keinen Sinn? Inwiefern?
> Warum nicht z.B. bei 1 eine Kante, die wieder direkt
> zurück zu 1 führt mit a,c,t
> anstatt 3 weitere Zustände?
Oh je! Jetzt sehe ich, was Du meinst – und Du hast natürlich absolut recht. So kann ich ganze sechs Zustände einsparen, was das Diagramm natürlich extrem übersichtlicher macht. Ich hatte mich schon gewundert, warum das alles so unübersichtlich aussieht.
Hier das komplett überarbeitete Zustandsdiagramm.
Das ist doch so richtig, oder?
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
Hallo Patrick,
akzeptiert Dein Automat das Wort
agtagt ?
Gruß
Anna
|
|
|
| |
|
Hallo nochmals,
> akzeptiert Dein Automat das Wort
> agtagt ?
den Fehler hatte ich ganz am Anfang schon mal gemacht – danke für den Hinweis. Hier die nochmals übearbeitete Grafik:
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
Hallo Patrick,
akzeptiert 
Gruß
Anna
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:42 Mo 12.11.2012 | | Autor: | Apfelchips |
Hallo Anna,
danke für Deine Hilfe. 
Gruß
Patrick
|
|
|
|
