r
N Beer Prüfungstermin Einze’ ifungsnummer

»

Kennzahl:

Herbst 46112
1996

Kennwort:

Arbeitsplatz-Nr.:

Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen

- Prüfungsaufgaben -
Fach: Informatik (nicht vertieft studiert)
Einzelprüfung: Grundlagen der Informatik

Anzahl der gestellten Themen (Aufgaben): 1

Anzahl der Druckseiten dieser Vorlage: 3

Bitte wenden!


Herbst 1996 Einzelprüfungsnr.: 46112 Seite: 2 \

Sämtliche Teilaufgaben sind zu bearbeiten!

Aufgabe 1

Hexadezimalzahlen sind Zeichenketten über dem Alphabet
A= {0, 1,2, 3, 4, 5,6, 7,8, 9, A, B,C, D, E, F}. -
_Eine Hexadezimalzahl h = hg...hyho mit hie 4 füri=0, ..., n stellt die Dezimalzahl
- hy * 169 + hoy * 16%) +... ola li ite
dar. Dabei hat A den Wert 10, B den Wert 11, C den Wert 12, D den Wert 13, E den Wert 14
und F den Wert 15.

a) Stellen Sie die folgenden Hexadezimalzahlen als Dezimalzahlen dar: 2F, A3E, 100B.
Stellen Sie die folgenden Dezimalzahlen als Hexadezimalzahlen dar: 26, 525, 10000.

Sei Ldie Sprache, die aus der Zahl O und aus allen Hexadezimalzahlen (beliebiger Länge), die
keine führenden Nullen haben, besteht.

b) Beschreiben Sie die Sprache £L entweder durch ein Syntaxdiagramm oder durch eine
kontextfreie Grammatik! : ,

c) Geben Sie einen deterministischen Automaten an, der genau die Sprache £ akzeptiert!

Die folgenden Programmieraufgaben können in einer beliebigen höheren Programmiersprache
gelöst werden, die die Deklaration von Aufzählungstypen und Feldtypen und die Deklaration
von Prozeduren und (rekursiven) Funktionen (bzw. Funktionsprozeduren) erlaubt (etwa Pascal,
Modula-2). Geben Sie die von Ihnen verwendete Programmiersprache an!

Als Standardfunktionen für die Arithmetik dürfen im folgenden nur die Operatoren +,-,*, DIV,
MOD und die üblichen Vergleichsoperatoren verwendet werden.

d) Es ist ein Datentyp mit Namen hexzahl zur Darstellung von Hexadezimalzahlen, die aus 10
Zeichen hg...hıho bestehen, zu entwickeln. Verwenden Sie dabei einen geeigneten
Aufzählungstyp für die Darstellung des Alphabets 4!

e) Schreiben Sie eine Prozedur zur Umrechnung von Hexadezimalzahlen in Dezimalzahlen!
Die Prozedur soll einen Wertparameter h vom Typ hexzahl haben und einen
Variablenparameter x, der nach Ablauf der Prozedur den umgerechneten Wert.von h
enthält. '

4

Fortsetzung nächste Seite!
Herbst 1996 .Einzelprüfungsnr.: 46112 . Seite: 3

Aufgabe 2

Gegeben seien die beiden folgenden (kontextfreien) Grammatiken G,, G, mit Variablenmenge (Nichtterminalsymbole) V = {S}, terminalem Zeichenvorrat £ = {a, b}, dem Startsymbol S und der Produktionenmenge

P, = {S>SS, S>aSb, S>e} bzw. P,= (S>aSbS, S>e}

(e = leeres Wort). :

a) Zeigen Sie, daB beide Grammatiken dieselbe Sprache L erzeugen!
b) Beschreiben Sie die Sprache L inhaltlich!

. c) Zeigen Sie, daB G, mehrdeutig ist (d. h. es gibt ein von G, erzeugtes Wort mit minde- -
stens zwei verschiedenen Ableitungsbäumen)!

d) Zeigen Sie, daß G, eindeutig (=nicht mehrdeutig) ist!