Professor Dr. F. Schweiggert -- Abteilung Angewandte Informationsverarbeitung
Blatt 4


[c]



Allg. Informatik für WiWi (WS 2000)


Abgabetermin 23. November 2000

3. Formale Sprachen - (18 Punkte)

Lösung:

a)
Gegeben sei Grammatik die G = (T,NT,P,S) mit
T = {0,1}, NT = {S,N,E} mit S Startsymbol\\
P = { S = 0N, S = 1E, S = , N = 0S, E = 1S}\\

b)
Eine Sprache L über dem Vokabular V={0,1} sei verbal wie folgt beschrieben:
L = {alle Folgen, die mit ``11'' beginnen, danach eine ungerade Zahl von Nullen (``0'') haben und mit einer ``1'' aufhören}
c)
In der Vorlesung wurden das Oktalzahl- und das Hexadezimalsystem behandelt und die Darstellung basierend auf der ASCII-Tabelle der Zahlen in den jeweiligen Zahlsystemen vorgestellt - also 0721 als Oktalzahl oder 0xF10 als Hexzahl. Geben Sie eine EBNF-Grammatik an, die den Aufbau von Dezimal-, Oktal- und Hexadezimalzahlen beschreibt! (3 Punkte)

$V = \{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,x\}$
$NT = \{S, HEX, OKT, DEZ, HexZiffer, OktZiffer, DezZiffer, ErsteDezZiffer\}$

$S \longrightarrow ~~ OKT ~~\vert~~ DEZ ~~\vert~~ HEX$
$OKT \longrightarrow ~~ 0 ~~ OktZiffer ~~\{~~ OktZiffer ~~\}$
$DEZ \longrightarrow ~~ 0 ~~ \vert ~~ ErsteDezZiffer ~~\{~~ DezZiffer ~~\} $
$HEX \longrightarrow ~~ 0x ~~ HexZiffer ~~\{~~ HexZiffer ~~\}$
$OktZiffer \longrightarrow ~~ 0 ~~\vert~~ 1 ~~\vert~~ 2 ~~\vert~~ 3 ~~\vert~~ 4 ~~\vert~~ 5 ~~\vert~~ 6 ~~\vert~~ 7$
$DezZiffer \longrightarrow ~~ OktZiffer ~~\vert~~ 8 ~~\vert~~ 9$
$ErsteDezZiffer \longrightarrow ~~ 1 ~~\vert~~ 2 ~~\vert~~ 3 ~~\vert~~ 4 ~~\vert~~ 5 ~~\vert~~ 6 ~~\vert~~ 7 ~~\vert~~ 8 ~~\vert~~ 9$
$HexZiffer \longrightarrow ~~ DezZiffer ~~\vert~~ A ~~\vert~~ B ~~\vert~~ C ~~\vert~~ D ~~\vert~~ E ~~\vert~~F$

d)
Gegeben sei folgende Dualzahl: 110100111
Geben Sie die entsprechende Oktal- und Hexadezimaldarstellung an! (2 Punkte)

Oktal: 0647
Hex: 0x1A7

e)
Gegeben sei die Hexzahl 0xFF.
Geben Sie diese Zahl in Dual-, Oktal- und Dezimalform an! (3 Punkte)
Dual: 1111 1111
Oktal: 0377
Dezimal: 255



Johannes Mayer 2000-11-23