Endliche Automaten - Suche Zustandsgraphen

Wissenschaft Informatik
#1

Schreibe am nächsten Mittwoch eine Klausur über Automaten (Grammatiken, Listen in Prolog, usw.).

Nun bin ich auf eine Übungsaufgabe gestoßen, zu der ich mindestens 20 Zustandsgraphen gezeichnet habe und noch nicht auf die richtige Lösung gekommen bin!

Die Aufgabe lautet:
Ein endlicher Automat ist gesucht, der alle Wörter akzeptiert, die aus geradzahlig vielen Nullen und geradzahlig vielen Einsen bestehten (Beispiele: 0101, 101101, 00010010).

Könnte mir jemand beschreiben wie der graph auszusehen hat???

Danke
MfG
Christian

#2

Hallo Christian,

Nun bin ich auf eine Übungsaufgabe gestoßen, zu der ich
mindestens 20 Zustandsgraphen gezeichnet habe und noch nicht
auf die richtige Lösung gekommen bin!

Die Aufgabe lautet:
Ein endlicher Automat ist gesucht, der alle Wörter akzeptiert,
die aus geradzahlig vielen Nullen und geradzahlig vielen
Einsen bestehten (Beispiele: 0101, 101101, 00010010).

Könnte mir jemand beschreiben wie der graph auszusehen hat???

Ich komm da mit 7 Zuständen und 3 Ereignissen zurecht.

Zustände:

  1. Bereit (Grundzustand)
  2. Nuller Gerade Einer Gerade
  3. Nuller UnGerade Einer Gerade
  4. Nuller Gerade Einer UnGerade
  5. Nuller UnGerade Einer UnGerade
  6. OK
  7. Fehler

Ereignisse:

  1. Null (eine Null eigegeben)
  2. Ein (eine Ein eigegeben)
  3. Fertig (Ende des Worts)

MfG Peter(TOO)

#3

Wenn ich den Zustandsgraphen zeichne, dann bin ich aber nicht mehr auf Eingaben, wie 0 oder 1 angewiesen! Dann besteht mein Graph nur aus Zuständen! Bitte um Rückantwort, ob ich da was falsch verstanden habe!

Ich komm da mit 7 Zuständen und 3 Ereignissen zurecht.

Zustände:

  1. Bereit (Grundzustand)
  2. Nuller Gerade Einer Gerade
  3. Nuller UnGerade Einer Gerade
  4. Nuller Gerade Einer UnGerade
  5. Nuller UnGerade Einer UnGerade
  6. OK
  7. Fehler

Ereignisse:

  1. Null (eine Null eigegeben)
  2. Ein (eine Ein eigegeben)
  3. Fertig (Ende des Worts)

MfG Peter(TOO)

#4

Wenn ich den Zustandsgraphen zeichne, dann bin ich aber nicht
mehr auf Eingaben, wie 0 oder 1 angewiesen! Dann besteht mein
Graph nur aus Zuständen! Bitte um Rückantwort, ob ich da was
falsch verstanden habe!

0 und 1 ist doch gerade dein Eingabealphabet! Die Nullen und Einsen werden an die Übergänge der Zustände geschrieben (Von NullGeradeEinsGerade geht ein 0-Übergang zu NullUngeradeEinsGerade). Das Fertig wird dadurch ausgedrückt, dass das was erkannt werden soll (War das beides gerade?) einfach in der Endzustandsmenge ist…

Ralph

#5

Bildchen

 ====== \_\_\_\_
 || || | |
--\> ||0g1g|| --0--\> |0u1g| 
 || || | |
 |0g1u|
#6

Hallo,
es reichen 4 Zustände:
q0,0: Gerade Anzahl von Nullen und Einsen.
q1,0: Ungerade Anzahl Nullen, gerade Anzahl von Einsen.
q0,1: Gerade Anzahl von Nullen, ungerade Anzahl von Einsen.
q1,1: Ungerade Anzahl von Nullen und Einsen.
Akzeptierend ist q0,0. Die 8 Transitionen sind:
(qn,m,0,q(n+1) mod 2,m) und (qn,m,1,qn,(m+1) mod 2) für n,m=0,1.

Gruss
Enno

#7

Jetzt verstehe ich das auch!!! Normalerweise habe ich nicht solche großen Probleme einen Zustandsgraphen hinzubekommen!!! Muss nur irgendwie mit Informatik überlastet sein, da ich es nur so wie du es erklärt hast Ralph verstehe! Vielen vielen Dank!