Grundlagen der theoretischen Informatik, SS 2005 — 4. Übungsblatt

Abgabe bis Dienstag, 17. Mai 2005, 10:15 Uhr

27.

Konstruieren Sie für den DEA M = (Q = {a, b, c}, Σ = {0, 1}, δ, a, {b}) einen regulären Ausdruck, der die von M akzeptierte Sprache beschreibt. Die Übergangsfunktion δ ist in der nebenstehenden Tabelle angegeben.

Wenden Sie den in der Vorlesung vorgestellten Algorithmus von Kleene auf die Zustände einmal in der Reihenfolge a, b, c und dann in der Reihenfolge c, a, b an. Vereinfachen Sie dabei die Zwischenergebnisse, so gut es geht. Versuchen Sie auch, ”direkt“ durch Betrachten des Zustandsdiagramms und Nachdenken einen möglichst einfachen regulären Ausdruck zu finden.

\begin{matrix}δ & 0 & 1 \\ a & a & b \\ b & c & b \\ c & b & a \end{matrix}

28. Erweitern Sie das in der Vorlesung vorgestellte lex-Programm^{1} zur Addition aller in der Eingabe vorkommenden Zahlen um folgende Funktionen:

(a) Es sind auch Zahlen in Exponentialnotation wie zum Beispiel 0.54e-7 = 0,54 × 10^{−7} zugelassen.

(b) Bei Eingabe von * wird die nächste Zahl nicht addiert, sondern multipliziert.

(c) Bei Eingabe von = wird das bisherige Ergebnis ausgedruckt.

(d) Es werden zusätzlich auch Kommentare im Stil von Haskell verstanden: Alles zwischen -- und dem Ende der Zeile wird ignoriert.

Die obigen Angaben lassen einige Fragen offen, zum Beispiel die Wechselworkung zwischen den verschiedenen Arten von Kommentaren. Ergänzen Sie zunächst die obige Aufgabenspezifikation in Worten, sodass das Verhalten des Programmes eindeutig daraus hervorgeht. Ihr Programm sollte dann dieser Spezifikation entsprechen.

29. Konstruieren Sie einen regulären Ausdruck für die Sprache L_{6} von Aufgabe 23f.

30. (Zusatzaufgabe) Konstruieren Sie DEAs und NEAs für folgende Sprachen über {0, 1}:

(a) die Wörter, deren vierter Buchstabe eine 0 ist;

(b) die Wörter, deren viertletzter Buchstabe eine 0 ist.

31. Definieren Sie formal die Nachfolgerrelation xqy ⊢ x′q′y′ für Konfigurationen einer Turingmaschine. (q, q′ ∈ Q, x ∈ {ε} ∪ (Γ − {B})Γ^{∗}, y ∈ {ε} ∪ Γ^{∗}(Γ − {B}).)

32. (10 Punkte) Multiplikation. Konstruieren Sie eine Turingmaschine, die zwei ”unäre“ Zahlen multipliziert. Bei Eingabe von 0^{m}#0^{n} soll die Ausgabe 0^{mn} berechnet werden.

33. Binäre Multiplikation.

In der Vorlesung wurde eine Turingmaschine vorgestellt, die die Summe zweier Zahlen in Binärdarstellung berechnet. Bei Eingabe von bin(x)#bin(y)$ und Start im Zustand q_{0} hält die Maschine im Zustand q_{F} mit der Ausgabe bin(x+y)#bin(y)$ und dem Kopf auf dem ersten Eingabesymbol. (Die Notation bin(x) ∈ {0, 1}^{∗} ist eine Darstellung von x ∈ ℕ in Binärdarstellung.) Der Bandinhalt rechts vom $-Zeichen bleibt dabei unverändert stehen. Erweitern Sie diese Maschine zu einer Maschine, die zwei Binärzahlen multipliziert: Bei Eingabe von bin(x)$bin(y) soll die Maschine die Ausgabe bin(x · y) berechnen. Ihre Maschine soll die Addiermaschine aus der Vorlesung als ”Unterprogramm“ benutzen, indem Sie an geeigneten Stellen in den Zustand q_{0} übergeht. Der Zustand q_{F} ist dann kein Haltezustand mehr, sondern die Rechnung wird danach fortgesetzt. Beschreiben Sie Ihren Algorithmus zunächst in Worten.

1http://www.inf.fu-berlin.de/lehre/SS05/GTI/flex/summe.flex