Mach den Automaten

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche

Druckversion

Farm-Fresh brain.png   Vorwissen

Bevor du hier loslegst, solltest du die folgenden Bausteine zuvor durchgearbeitet haben:

Farm-Fresh pencil add.png   Aufgabe

Gegeben sei das Alphabet \Sigma=\{a,b\}. Konstruiere jeweils einen deterministischen endlichen Automaten A_i, der die folgenden Sprachen erkennt:

  1. L(A_1)=\{a^mb^n|m,n>0\}
  2. L(A_2)=\{a^mb^n|m,n\geq 0\}
  3. L(A_3)=\{a^nb^n|n\geq 0\}
  4. L(A_4)=\{a(ab)^nb|n\geq 0\}
  5. L(A_5)=\{w\in \Sigma^*|w enthält eine gerade Anzahl von as und eine ungerade Anzahl von bs\}
  6. L(A_6)=\{w\in \Sigma^*|\ |w| lässt beim Dividieren durch 4 den Rest 1\}
  7. L(A_7)=\{w\in \Sigma^*|\ w besteht aus mindestens zwei bs. Es folgen aber niemals zwei bs direkt aufeinander\}


Überprüfe dabei jeweils:

  1. Hast du den Startzustand angegeben?
  2. Hast du die Endzustände markiert?
  3. Gibt es in jedem Zustand für jeden Buchstaben aus \Sigma einen Folgezustand?
  4. Teste darüber hinaus mit verschiedenen Wörtern, die in der Sprache sind, und auch mit solchen, die nicht in der Sprache sind. Funktioniert dein Automat zuverlässig? Wie kannst du jemanden davon überzeugen, dass er es tut?
Farm-Fresh hand point.png  Tipps

Du benötigst einen Tipp? Den bekommst du hier: Tipps (Schau dir die Tipps aber nur an, wenn du es wirklich selbst versucht hast und nicht weiterkommst!)