Prof. Dr. Franz Schweiggert Abteilung Angewandte Informationsverarbeitung 12. November 2003
Dr. Andreas Borchert, Michael Wiedemann Blatt 5






Allgemeine Informatik I (WS 2003/2004)


Abgabetermin: 19. November 2003

9 Formale Sprachen, die zweite - 2 Punkte

Gegeben sei die Grammatik $G := (NT, T, S, P)$ aus dem vorherigen Übungsblatt mit folgenden Eigenschaften:

• $NT : \{L, E\}$
• $T : \{a, b, \mbox{\lq\lq ,''}, \mbox{\lq\lq (''}, \mbox{\lq\lq )''}\}$
• $S : \{L\}$
• $P : \{L \rightarrow E, L \rightarrow L \mbox{\lq\lq ,''} E, E \rightarrow a, E \rightarrow b, E \rightarrow \mbox{\lq\lq (''} L \mbox{\lq\lq )''}\}$

Stellt diese Grammatik bitte in EBNF-Form dar. Welche Form der Rekursion aus der obigen Definition lässt sich dabei dank EBNF in der Notation vermeiden?

10 Formale Sprachen, die dritte - 6 Punkte

Gegeben sei eine Sprache $L$ mit dem Vokabular $V$ = {a, b} mit folgenden verbal beschriebenen Eigenschaften:

``Zur Sprache $L$ gehören alle Folgen aus dem Vokabular $V$, für die gilt: Die Folge beginnt mit einem b, gefolgt von einem a, danach eine ungerade Anzahl an b, abgeschlossen durch ein a.''

Ihr solltet folgendes erledigen:

• Zeichnet ein Syntax-Diagramm, das diese Sprache beschreibt. Tipp: Es könnte von Vorteil sein, zunächst eine EBNF-Grammatik zu dieser Sprache zu finden.
• Findet einen regulären Ausdruck, der diese Sprache spezifiziert.
• Zeichnet einen deterministischen endlichen Automaten, der Sätze der Sprache $L$ erkennt.

11 Malen nach Zahlen - 2 Punkte

Keine Angst, Ihr habt für dieses Blatt schon mehr als genug gemalt, deswegen werden wir jetzt eine Runde rechnen. Ihr habt in der Vorlesung weitere Zahlensysteme kennengelernt. Diese werden wir uns nun etwas näher anschauen.

• Konvertiert die angegebenen Zahlen in Binär-, Oktal-, Dezimal- und Hexadezimal-Zahlen:
  $71_{10}$
  $11100010_2$
  $75_8$
  $AF_{16}$
• Zum guten Schluss üben wir das Addieren zweier Binärzahlen:

  $10100011_2$ + $10111100_2$

  Die Addition sollte selbstverständlich binär erfolgen. Welche Dezimalzahl resultiert aus der Addition?

Viel Erfolg!