Übung zur Vorlesung

Theoretische Informatik I

Prof. Christoph Kreitz / Jens Otten Universität Potsdam, Theoretische Informatik — Sommersemester 2004 Blatt 11 — Abgabetermin: Donnerstag, 8. Juli 2004, 22.00 Uhr

Quiz 11

Markieren Sie die nachfolgenden Aussagen als ”wahr” oder ”falsch”.

[ ] Die Simulation einer Linksableitung einer kontextfreien Grammatik kann durch einen Pushdown-Automaten (PDA) mit nur einem Zustand realisiert werden.

[ ] Bei der Umwandlung eines PDAs in eine äquivalente kontextfreie Grammatik werden bis zu |Q|^{2} |Γ| + 1 Variablen benötigt.

[ ] Jede kontextfreie Grammatik kann in einen äquivalenten deterministischen Pushdown-Automaten (DPDA) umgewandelt werden.

[ ] Jeder DPDA kann in einen äquivalenten DEA umgewandelt werden.

[ ] Sie werden diese Aussage als ”falsch” markieren.

Aufgabe 11.1 (Umwandlung PDA in Grammatik)

Sei L={w∈{a, b, c, d}^{∗} | w=a^{n}b^{m}c^{l}d^{l}b^{m}a^{n} mit n, m, l∈IN_{0}}.

1. Geben Sie eine kontextfreie Grammatik G=(V, T, P, S) für L an mit L=L(G).

2. Wandeln Sie Ihre Grammatik in einen PDA P_{ϵ}={Q, Σ, Γ, δ, q_{0}, Z_{0}, ∅} um, der ein Wort w bei leerem Stack genau dann akzeptiert, wenn w∈L. Benutzen Sie die in der Vorlesung vorgestellte Methode.

Aufgabe 11.2 (Deterministische Pushdown-Automaten)

1. Sei P =({q_{0}, q_{1}, q_{2}}, {a, b, c}, {Z, Z_{0}}, δ, q_{0}, Z_{0}, {q_{2}}) ein PDA mit der Übergangsfunktion δ definiert durch das folgende Übergangsdiagramm.

[figure: Start; c, Z_{0}/Z_{0}; c, Z/Z; ϵ, Z_{0}/ZZZ_{0}; a, Z_{0}/ZZ_{0}; a, Z/ZZ; b, Z/ϵ; q_{2}; q_{1}; q_{0}]

Geben Sie die von dem Automaten akzeptierte Sprache L(P) an.

2. Geben Sie einen deterministischen Pushdown-Automaten für die folgende Sprache an: L={0^{n}1^{k} | n, k∈IN_{0} und n≠k}.

Übung zur Vorlesung Theoretische Informatik I Blatt 11

Aufgabe 11.3 (Umwandlung PDA in Grammatik) [3 Punkte]

Sei L={a^{n}b^{m}c^{2(n+m)} | n, m∈IN_{0}}.

1. Geben Sie eine kontextfreie Grammatik G=(V, T, P, S) für L an mit L=L(G).

2. Wandeln Sie Ihre Grammatik in einen PDA P_{ϵ}={Q, Σ, Γ, δ, q_{0}, Z_{0}, ∅} um, der ein Wort w bei leerem Stack genau dann akzeptiert, wenn w∈L. Benutzen Sie die in der Vorlesung vorgestellte Methode.

Aufgabe 11.4 (Deterministische Pushdown-Automaten) [3 Punkte]

1. Sei P =({q_{0}, q_{1}, q_{2}}, {a, b, c}, {Y, Z, Z_{0}}, δ, q_{0}, Z_{0}, {q_{2}}) ein PDA mit der Übergangsfunktion δ definiert durch das folgende Übergangsdiagramm.

[figure: Start; c, Z/Z; ϵ, Z_{0}/ZZ_{0}; a, Z/Y Z; a, Y/ZY; b, Z/ZZ; q_{2}; q_{1}; q_{0}]

Geben Sie die von dem Automaten akzeptierte Sprache L(P) und deren Typ an.

2. Geben Sie einen deterministischen Pushdown-Automaten für die folgende Sprache an: L={0^{n}1^{m}0^{2n} | n, m∈IN und n, m≥1}.

Aufgabe 11.5 (Pushdown-Automaten) [3 Punkte]

Zeigen Sie, dass es für jede kontextfreie Grammatik G = (V, T, P, S) einen PDA mit höchstens zwei Zuständen und ohne ϵ-Übergänge gibt, der L(G) durch einen (akzeptierenden) Endzustand akzeptiert.

Tipp: Benutzen Sie zur Lösung das Ergebnis zur Umwandlung einer kontextfreien Grammatik in einen PDA.

Haben Sie Fragen, Anregungen oder Probleme? Lassen Sie es uns wissen!

• Prof. Christoph Kreitz, Raum 1.18, kreitz@cs.uni-potsdam.de, Tel. 0331/977 3060 Sprechstunde: immer, wenn die Türe des Raumes 1.18 offen steht, und am Mittwoch 11.00 bis 12.30 Uhr

• Jens Otten, Raum 1.20, jeotten@cs.uni-potsdam.de, Tel. 0331/977 3072 Sprechstunde: immer, wenn die Türe des Raumes 1.20 offen steht, und am Dienstag 14.00 bis 16.00 Uhr.