close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Aufgabe 74 - Aufgabe 78 sind wie Aufgabe 52 als Mini

EinbettenHerunterladen
Übung 9 zu TI
SS 2012
Prof. Dr. H. Faßbender
Besprechung am 29.05.2012
Seite 1
Aufgabe 74 - Aufgabe 78 sind wie Aufgabe 52 als Mini-Seminaraufgabe jeweils
von 2 Studierenden zu bearbeiten. Hierzu ist die Lösung in Form einer kurzen
Ausarbeitung schriftlich darzustellen und in der Übung vorzutragen.
Weitere Mini-Seminaraufgaben folgen auf dem letzten Übungsblatt.
Die Übernahme einer Aufgabe ist per Email anzumelden. Sollten am Ende nicht
genügend Aufgaben übrig bleiben, werden die restlichen verlost. Die Bearbeitung einer Aufgabe zählt als 5. Praktikumsversuch, so dass die Endtestatvergabe nur bei erfolgreicher Bearbeitung erfolgt.
Aufgabe 69
(Typ 2-Pumping Lemma)
Zeigen Sie, dass das obere der beiden Vorkommen der Variablen im Typ 2-Pumping Lemma
maximal k Schritte von der Blattebene entfernt ist.
Lösung:
Es gibt 2 Fälle:
1. Die Variable V befindet sich an (k+1)-ter Position, also k-Schritte (Schritte von 0 bis k) von
der Blattebene entfernt, und kommt dort zum 2. Mal vor.
2. Die Variable V befindet sich an (k+1)-ter Position, also k-Schritte (Schritte von 0 bis k) von
der Blattebene entfernt, und kommt dort zum 1. Mal vor
zu 1. Fertig!
zu 2. Unterhalb von V gibt es k Positionen, an denen k-1 verschiedene Variablen vorkommen
können. D.h.: dort kommt eine Variable V zweimal vor. Nehme oberes Vorkommen von
V , das ist weniger als k von Blattebene entfernt. Fertig.
Aufgabe 70
(Typ 1-Sprache)
Zeigen Sie, dass die Sprache L = {am bm cm | m ≥ 1} vom Typ 1 ist.
Lösung:
L = {am bm cm |m ≥ 1 }
Folgende Grammatik ist Typ 1 und erzeugt diese Sprache:
G = ({S, B, C {a, b, c}, S, P ), mit P = {
S → aSBC,
erzeuge gleich viele a, B, C
S → aBC,
I.A. zu oben
CB → BC,
bringe Cs rechts von den Bs
aB → ab,
ersetze B durch b
bB → bb,
ersetze B durch b
bC → bc,
ersetze B durch b
cC → cc
ersetze C durch c
}
Übung 9 zu TI
SS 2012
Prof. Dr. H. Faßbender
Aufgabe 71
Besprechung am 29.05.2012
Seite 2
((Semi-)Entscheidbarkeit)
Zeigen Sie, wenn eine Sprachklasse semientscheidbar und unter Komplement abgeschlossen
ist, dann ist sie auch entscheidbar.
Lösung:
Aus TIWS bekannt, wenn Sprache semientscheidbar, dann aufzählbar. D.h. es gibt Aufzählung
¯ Lasse die Aufzählung im Reißverschlussverfahren laufen. Dann kommt w auf jeden
für L und L.
¯ aufgezählt wurde.
Fall mal vor. Ausgabe hängt dann davon, ob w durch L oder L
Pseudocode:
[Start Endless_LOOP]
erzeuge nächstes Wort in L [ ==> l]
[if l == w]
[return true]
[end if]
erzeuge nächstes Wort in not L [ ==> m]
[if m == w]
[return false]
[end if]
[end Endless_LOOP]
Aufgabe 72
(alternativer Beweis des Typ 3-Pumping Lemmas)
Beim Beweis des Typ 3-Pumping Lemmas wurde die Anzahl der Zustände eines DEAs als
Pumping Index zugrunde gelegt. Beim Beweis des Typ 2-Pumping Lemmas die Knotenanzahl
eines Teilbaumes des Parse-Baums.
Führen Sie einen alternativen Beweis des Typ 3-Pumping Lemmas, der ebenfalls den ParseBaum zugrunde legt. Überlegen Sie, wie sich der dabei verwendete Pumping Index zu dem
aus dem Beweis der Vorlesung verhält.
Lösung:
Der Ableitungsbaum einer rechtslinearen Grammatik ist ein Kamm, siehe Abbildung 1. Insofern wählt man n nicht als 2|V | , sondern als |V | und w ∈ L mit |w| ≥ n, dann exisitert im
Ableitungsbaum mind. eine Variable A die doppelt durchlaufen wird.
• Zerlege den Ableitungsbaum so, dass bis zum ersten Auftreten von A das Wort u gelesen
wurde und bis zum zweiten Auftreten das Wort uv.
• Damit sind die Bedingungen 1 und 2 erfüllt.
• Die Bedingung 3 ergibt sich dann völlig analog zum Beweis des Typ 2-Pumping Lemmas.
Aufgabe 73
(Abschlusseigenschaften von Typ 1-Sprachen)
• Geben Sie zwei Grammatiken G1 und G2 an, die maximal Typ 1 sind.
Übung 9 zu TI
SS 2012
Prof. Dr. H. Faßbender
Besprechung am 29.05.2012
Seite 3
Abbildung 1: Ableitungsbaum
• Geben Sie eine Typ 1-Grammatik an für die Sprache L(G1 ) ∪ L(G2 ).
• Geben Sie eine Typ 1-Grammatik an für die Sprache L(G1 ) ◦ L(G2 ).
• Geben Sie eine Typ 1-Grammatik an für die Sprache L(G1 )∗ .
Lösung:
G1 = ({S, A}, {a}, S, P )
P = (S → A, A → aA, aA → a)
G2 = ({S, B}, {b}, S, P )
P = (S → B, B → bB, bB → b)
L(G1 ) ∪ L(G2 ) = L(GV ereinigung )
GV ereinigung = ({S, X}, {a, b}, S, P )
P = (S → X, X → a, X → b)
L(G1 ) ◦ L(G2 ) = L(GKonkatenation )
GKonkatenation = ({a, b}, {S, X}, S, P )
P = (S → X, X → ab)
G∗1 = L(GKleene )
GKleene = ({a}, {S, X}, S, P )
P = (S → ε, S → X,
X → Xa, X → a)
Aufgabe 74
(Typ 0 -> TM)
• Geben Sie eine Grammatik G an, die maximal Typ 0 ist.
• Geben Sie die Turing-Maschine an, die sich nach der Konstruktion der Vorlesung aus
Ihrer Grammatik G ergibt und begründen Sie, wo diese die LBA-Eigenschaft verletzt.
Übung 9 zu TI
SS 2012
Prof. Dr. H. Faßbender
Aufgabe 75
Besprechung am 29.05.2012
Seite 4
(Typ 1 -> LBA)
• Geben Sie eine Grammatik G an, die maximal Typ 1 ist.
• Geben Sie den LBA an, der sich nach der Konstruktion der Vorlesung aus Ihrer Grammatik G ergibt.
Aufgabe 76
(TM -> Typ 0)
• Geben Sie eine TM M an, die kein LBA ist.
• Geben Sie die Grammatik G an, die sich nach der Konstruktion der Vorlesung aus Ihrer
TM M ergibt.
• Von welchem maximalen Typ ist die Grammatik G?
Aufgabe 77
(LBA -> Typ 1)
• Geben Sie einen LBA M an.
• Geben Sie die Grammatik G an, die sich nach der Konstruktion der Vorlesung aus Ihrem
LBA M ergibt.
• Von welchem maximalen Typ ist die Grammatik G?
Aufgabe 78
(Mehrband-TM -> Einband-TM)
Zeigen Sie, dass man jede Mehrband-TM in eine äquivalente Einband-TM transformieren kann.
Lösung:
Document
Kategorie
Sport
Seitenansichten
10
Dateigröße
120 KB
Tags
1/--Seiten
melden