ueb-3-00

Prof. Dr. Ralf Der - Institut für Informatik - Universität Leipzig

Übungsblätter zur Vorlesung Digitale Informationsverarbeitung

(Magister)

Wintersemester 2002/03 - Serie 5

Stellen Sie folgende verbale Aussage in BNF Notation und als regulären Ausdruck dar: Ein Bezeichner ist ein String, der mit einem Buchstaben beginnt, gefolgt von einer Kette von n Zeichen (mit n>=0), die aus allen Buchstaben des Alphabetes, den Ziffern 0 bis 9 und dem Unterstrich _ in beliebiger Mischung besteht. (je 2 Pkte.)
Geben Sie in BNF (Backus-Naur- Form) oder in der erweiterten BNF (EBNF) eine Definition der Dezimalzahlen ohne führende Nullen (Beispiel 3.14). (3 Pkte.)
Beschreiben Sie verbal die Menge L von Binärzahlen, die durch den EBNF Ausdruck {(1|01|001)}(epsilon|0|00) definiert wird und geben Sie einige Beispiele für Binärzahlen an, die zu L gehören bzw. nicht dazugehören (mit Begründung). Es gilt {(...)}=(...)|(...)(...)|(...)(...)(...)|... (3 Pkte.)
Geben Sie reguläre Ausdrücke an, die folgende Strings beschreiben (je 1 Pkt.).

Alle Strings von 0-en und 1-en, die mit einer 0 enden.
Alle Strings von 0-en und 1-en, die mindestens eine 1 enthalten.
Alle Strings von 0-en und 1-en, die höchstens eine 1 enthalten.
Alle Strings von 0-en und 1-en, bei denen die dritte Position von rechts eine 1 ist.

Geben Sie die Syntax der im Kap. Berechenbarkeit eingeführten WHILE Programme in EBNF Notation an. (5 Pkte.)
Huffmann-Code: In einer unendlich langen Zeichenkette treten die Zeichen a,b,c,d,e,f mit den Wahrscheinlichkeiten 0.1, 0.2, 0.05, 0.3, 0.25, 0.1 auf. Geben Sie den Code nach Huffmann und den dazugehörigen Codebaum an. (4 Pkte.)
Wiederholung Zahlendarstellung:

Wieviel mögliche Belegungen von n Bits mit 0 und 1 gibt es (Mit Begründung, verbal oder durch Induktion über n)? (2 Pkte.)
Berechnen Sie die Anzahl Druckseiten (im 8-Bit ASCII Code), die auf eine HD Diskette (1.44 MB), eine CD ROM (700 MB) bzw. auf eine Festplatte mit 1 GB Speicherkapazität passen. Eine Druckseite soll dabei 60 Zeilen mit je 70 Zeichen umfassen. (2 Pkte.)
Die Darstellung einer Zahl im Hexadezimalsystem läßt sich unmittlebar aus ihrer Binärdarstellung ableiten und umgekehrt. Geben Sie einen Algorithmus zur Umwandlung der Darstellungen einer Zahl vom Hexadezimalsystem in das Dualsystem und umgekehrt an. (4 Pkte.)