close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Grundlagen der Programmierung 1 (PRG-1) - G-CSC Home

EinbettenHerunterladen
Goethe-Center for Scientific Computing (G-CSC)
Goethe-Universit¨at Frankfurt am Main
Grundlagen der Programmierung 1 (PRG-1)
¨
(Ubung,
Wintersemester 2014/2015)
S. Reiter, M. Rupp, Dr. A. Vogel, Dr. K. Xylouris, Prof. Dr. G. Wittum
Aufgabenblatt 1 (Abgabe: Mo., 3.11., 12h)
Aufgabe 1 (5+5 Punkte, LEO ist abz¨ahlbar)
a) Skizzieren Sie die schematische Darstellung eines Ableitungsbaums, der
alle W¨orter der Sprache LEO enth¨alt. Beschreiben Sie in Worten, wie der
Baum konstruiert wird.
b) Geben Sie in Worten einen Algorithmus an, der jedem Wort aus dem
LEO-System in eineindeutiger Weise eine nat¨
urliche Zahl zuordnet. Dabei
bedeutet eineindeutig, dass Ihr Verfahren jedem Wort genau eine nat¨
urliche
Zahl und jeder nat¨
urlichen Zahl genau ein Wort zuordnen soll. (Tipp: Sie
k¨onnen den Ableitungsbaum als bekannt voraussetzen.)
Aufgabe 2 (10 Punkte, Addition mit Turingmaschine)
Eine Turingmaschine mit einseitig unendlichem Band besteht aus einem unendlich langen Speicherband, bei dem in jedem Speicherfeld eine Eins oder
eine Null stehen kann. Zudem besitzt die Maschine einen Lese-/Schreibkopf,
der das aktuelle Feld lesen und beschreiben kann. Die Maschine befindet sich
immer in einem definierten Zustand.
Jeder Schritt der Turingmaschine f¨
uhrt folgende Anweisungen im aktuellen
Zustand aus:
(1) Es wird das Zeichen an der aktuellen Position gelesen.
(2) Es wird ein Zeichen auf die aktuelle Position geschrieben.
(3) Der Lesekopf wird nach Links oder Rechts bewegt.
(4) Die Maschine geht in einen Zustand u
¨ber (kann auch der aktuelle sein).
Die Schritte (2)-(4) h¨angen dabei davon ab, in welchem Zustand sich die
Maschine aktuell befindet und welches Zeichen gelesen wird.
Die Maschine befinde sich am Anfang in Zustand 1 und der Endzustand sei
durch E bezeichnet. Der Zustandsablauf kann somit durch eine Tabelle von
Zustandsanweisungen beschrieben werden:
Zustand Eingabe
1
0
1
2
...
Operation
1, r
1, l
..
Folgezustand
1
2
E
Die Eingabe f¨
ur die Turingmaschine bestehe aus einer Kette von n ≥ 1 und
m ≥ 0 Einsen, die von einer Null getrennt sind. Die Einserketten sollen
nat¨
urliche Zahlen darstellen.
|1|1|1|....|1| 0 |1|1|1|....|1| 0|0|...
n
m
Geben Sie die obige Zustandstabelle an, die die beiden Zahlen auf dem Eingabeband addiert (d.h. es soll die Folge von n + m Einsen auf dem Band
stehen). Bei Programmende soll der Lese-/Schreibkopf wieder ganz links auf
dem Band stehen.
Aufgabe 3 (10 Punkte, das PG-System)
Es sei Σ = {−, p, g} ein Alphabet. Wir betrachten nun das sogenannte PGSystem von Worten aus Σ∗ . Beispiele f¨
ur W¨orter im PG-System sind:
−p−g−−
− −p − −g − − − −
− − − p − − − − − g − − − − − − − −.
Im allgemeinen haben die Worte des PG-Systems die Gestalt
−... − p − ... − g − ...−,
wobei die Anzahl der − Zeichen nach dem g die Summe der − Zeichen vor
dem p und zwischen dem p und g ist. Sie k¨onnen also p als “plus“ und g als
“gleich“ interpretieren und die Ketten aus “−“-Zeichen kodieren die nat¨
urlichen Zahlen. Entwerfen Sie, analog zum LEO-System aus der Vorlesung,
einen Satz von (m¨oglichst wenigen) Regeln, die die Worte des PG-Systems
erzeugen.
¨
Hinweis: Die Abgabe der schriftlichen Ubungszettel
erfolgt vor der
Vorlesung. Bitte schreiben Sie auf die L¨osung Ihren Namen und die
¨
Ubungsgruppe. Heften Sie gegebenenfalls mehrere Zettel zusammen.
Document
Kategorie
Technik
Seitenansichten
14
Dateigröße
75 KB
Tags
1/--Seiten
melden