« »

GRABS Übungsaufgaben Automaten und Schaltwerke Endlicher Automat 3

Endlicher Automat 3

Endlicher Automat mit den Zuständen Init sowie Z1 bis Z4. Die Zustände zeigen zusätzlich die Ziffer 0 mit Ausnahme von Z4, der eine 1 zeigt. Folgende Transitionen sind definiert: Init nach Init mit Label “T”. Init nach Z1 mit Label “H”. Z1 nach Z2 mit Label “T”. Z2 nach Z3 mit Label “H”. Z3 nach Z4 mit Label “H”. Z4 nach Z1 mit Label “H”.

Der endliche Automat in der Abbildung soll eine bestimmte Folge von Buchstaben H und T erkennen. Er soll den Ausgabewert 1 dann und nur dann erzeugen, wenn die Zeichenfolge HTHH erkannt wurde. Der Startzustand des Automaten ist Init.

Beispiel:

Eingabefolge: H H H H H T H H T H H H H H T H H T
Ausgabe:      0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0

Diese Aufgabe war Teil der Klausur im Sommersemester 2025 (Zweittermin).

a)

Level 3: Anwenden

Ergänzen Sie den Automaten mit den notwendigen Transitionen, sodass die Erkennung für Eingabefolgen beliebiger Länge funktioniert. Geben Sie dazu für jede Transition den Start- und Endzustand und die notwendige Bedingung wie folgt an: Z4, Z1, H.

Hinweis

Sie benötigen vier Transitionen. Die angegebene Beispieltransition existiert bereits im Automaten.

Lösung

Folgende Transitionen fehlen:

  1. Z2, Init, T
  2. Z3, Z2, T
  3. Z4, Z2, T
  4. Z1, Z1, H

b)

Level 1: Wissen

Wie viele Bits werden für das Register benötigt, das den Zustand des Automaten speichert?

Lösung

Die Anzahl der Bits berechnet sich durch $\lceil \log_2{|Q|}\rceil$ mit $Q$ als Menge der Zustände. Der angegebene Automat hat 5 Zustände. $\log_2{5} \approx 2{,}321928095$, somit brauchen wir 3 Bits.

Lernziele

In dieser Aufgabe …

  • festigen die Studierenden ihre Kenntnisse über endliche Automaten.
  • wiederholen die Studierenden die Zusammenhänge zwischen Informationsgehalt und Binärdarstellung.