Benutzer-Werkzeuge

Webseiten-Werkzeuge


dualzahlen
Aufgabe

Grundkurs Informatik, Saarland, 2004 (ohne Lösung)

Neben der Dezimalzahldarstellung (z. B. 43,5 ; 0,567 ; 34 ; 0) gibt es u. a. auch eine Dualzahldarstellung (z. B. 1011,101 ; 0,001; 100,0). Da sie auf der Basis 2 beruht, enthält sie nur die Ziffern 0 und 1. Die folgenden Aufgaben nehmen Bezug auf diese Darstellung.

1. Gegeben ist der Übergangsgraph des endlichen Automaten M (Komma steht für das Zeichen ',').

1.1 Prüfen Sie, ob folgende Worte von M akzeptiert werden:

w1= 0,0010
w2= 0,1101

1.2 Geben Sie die Bestandteile des Automaten M an.

1.3 Begründen Sie, weshalb der Automat nichtdeterministisch ist.
Konstruieren Sie zu M einen gleichwertigen deterministischen Automaten M'.
Skizzieren Sie den zugehörigen Übergangsgraph (Zustandsgraph).

1.4 Geben Sie einen regulären Ausdruck an, der die durch den Automaten M akzeptierte Sprache beschreibt.

2. Geben Sie einen regulären Ausdruck an, der alle Dualzahlen beschreibt. Für diese soll gelten:

  • wenn ein Komma gesetzt wird, dann müssen vor und nach dem Komma Ziffern stehen
  • die Darstellung muss mit der Ziffer 1 beginnen (außer bei 0,… und 0 selbst)
  • die letzte Ziffer hinter dem Komman kann auch die Ziffer 0 sein.
Bemerkungen

Röhner:

  • In Aufgabe 1.1 soll geprüft werden, ob die Worte w1 und w2 akzeptiert werden. Offen bleibt, welche Leistung erwartet wird. Soll nur angegeben werden dass w2 akzeptiert wird und w1 nicht oder muss dies beispielsweise durch Angabe von Zustandsfolgen nachgewiesen werden.
  • Das Begründen in Aufgabe 1.3 liegt im Anforderungsbereich I. Deshalb ist Begründen hier der falsche Operator.
  • Statt Konstruieren kann man in Aufgabe 1.3 gut Entwerfen benutzen
  • In den Aufgaben 1.4 und 2. wird der Operator Angeben für Anforderungen benutzt, die nicht im Anforderungsbereich I liegen.
dualzahlen.txt · Zuletzt geändert: 2014/09/01 14:53 von admin