« »

GRABS Übungsaufgaben Automaten und Schaltwerke Endlicher Automat 4

Endlicher Automat 4

Gegeben ist das Zustandsübergangsdiagramm für einen endlichen Automaten:

Endlicher Automat mit den Zuständen (S=(0,0), Q=0), (S=(0,1), Q=0), (S=(1,0), Q=0), (S=(1,1), Q=1). Folgende Transitionen sind definiert: (0,0) mit X=0 nach (0,0). (0,0) mit X=1 nach (0,1). (0,1) mit X=0 nach (0,0). (0,1) mit X=1 nach (1,0). (1,0) mit X=1 nach (1,0). (1,0) mit X=0 nach (1,1). (1,1) mit X=1 nach (0,1). (1,1) mit X=0 nach (0,0).

Der endliche Automat in der Abbildung erkennt eine bestimmte Bitfolge. Es existiert nur ein Eingang X, der den Wert 0 oder 1 annehmen kann. Der Ausgang Q nimmt den Wert 1 an, wenn die Bitfolge erkannt wurde. Die Zustände sind direkt mit zwei Bits S1 und S0 codiert mit (S1,S0) = (0,0), (0,1), (1,0) und (1,1). Der Startzustand ist (0,0).

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

a)

Level 1: Wissen

Ergänzen Sie die folgende Zustandsübergangstabelle.

S1S0XS1’S0’
00000
00101
010(a)0
01110
1001(b)
10110
110(c)0
1110(d)
Lösung
  • a=0
  • b=1
  • c=0
  • d=1

b)

Level 1: Wissen

Erstellen Sie die Logikfunktionen für S1' und S0'. Verwenden Sie, wenn benötigt, Klammerung von Ausdrücken und die Symbole *, + und / für die Logikfunkionen AND, OR und NOT.

Lösung

Logikfunktion für S1':

(/S1*S0*X) + (S1*/S0*/X) + (S1*/S0*X)

Logikfunktion für S0':

(/S1*/S0*X) + (S1*/S0*/X) + (S1*S0*X)

c)

Level 3: Anwenden

Welche Bitfolge wird von diesem Automaten erkannt?

Lösung

Der Automat erkennt Folgen aus mindestens einer 0, mindestens zweimal 1 und einer abschließenden 0.

Lernziele

In dieser Aufgabe …

  • festigen die Studierenden ihre Kenntnisse über endliche Automaten.
  • üben die Studierenden, die Sprache zu beschreiben, die ein Automat akzeptiert.
  • wiederholen die Studierenden die Schaltungssynthese aus einem Automaten.