Transcript
Universität des Saarlandes Fakultät 6.2 – Informatik
Theoretische Informatik (WS 2015) Team der Tutoren
Lösungsvorschlag 5
Aufgabe 5.1 Betrachten wir die Sprache L = {an bm cn+m |n, m ∈ N }. (a) (b) (c) (d)
(16 Punkte)
Geben Sie eine Grammatik G an, die L generiert. Beschreiben Sie informell, warum Ihre Grammatik genau L erzeugt. Skizzieren Sie eine Ableitung von aabbbccccc. Beweisen Sie, dass Ihre Grammatik genau L erzeugt.
Lösungsvorschlag 5.1 (a) G = ({a, b, c}, {S, X, Y }, S, P ) mit P = {S → X, S → , X → aXc, X → Y, Y → bY c, Y → } (b) Die Grammatik G fängt damit an, dass sie dem Wort beliebig viele a’s und genau so viele c’s hinzufügt. Dann fügt sie zwischen die a’s und c’s entweder oder beliebig viele b’s und noch einmal genau so viele c’s ein. So ergibt sich #a (u) + #b (u) = #c (u). Dabei ist außerdem gewährleistet, dass die Reihenfolge der Zeichen im Wort eingehalten wird, da niemals ein b oder c vor einem a und niemals ein c vor einem b stehen kann. (c) Für das Wort aabbbccccc gilt folgender Ableitungsbaum: S X c
X
a a
c
X Y b
c
Y b
Y
c
b Y c (d) Wir folgen dem Beweisschema aus Vorlesung 9: Behauptung: L(G) = {an bm cn+m |n, m ∈ N }. Beweis: "⊆": Zunächst zeigen wir, dass L(G) ⊆ {an bm cn+m |n, m ∈ N }, also dass jedes Wort, das mit G erzeugt werden kann, auch ein Wort der Sprache L ist. Dafür zeigen wir, dass folgende Aussagen nach jedem Ableitungsschritt für den abgeleiteten String u gelten: (i) #a (u) + #b (u) = #c (u) (ii) Kein b oder c kommt vor einem a und kein c kommt vor einem b. Regeln, die S ersetzen: Die Regeln S → X, S → Y und S → können nur höchstens einmal zu Beginn der Ableitung angewendet werden, da es keine Regel gibt, die ein S auf der rechten Seite
1/4
enthält. Sowohl für das Wort X als auch für sind (i) und (ii) offensichtlich erfüllt. Regeln, die X ersetzen: Sei der bisher abgeleitete String w = uXu0 . Da die einzigen Regeln, die ein X produzieren die Regeln S → X und X → aXc sind, folgt, dass u ∈ {a}∗ und u0 ∈ {c}∗ und dass |u| = |u0 |. Insbesondere kann w kein b enthalten. w erfüllt also (i) und (ii) Wir können also entweder X → aXc oder X → Y anwenden. Dabei wird das Wort uaXcu0 , bzw. uY u0 abgeleitet. Sowohl (i) als auch (ii) sind hierbei also erfüllt. Regeln, die Y ersetzen: Sei der bisher abgeleitete String w = uY u0 . Die einzigen Regeln, die w produziert haben können, sind X → Y und Y → bY c. Falls w durch X → Y produziert wurde, gilt, dass w aus w0 = uXu0 abgeleitet wurde. Da wir oben schon gezeigt haben, dass w0 (i) und (ii) erfüllt, muss auch w (i) und (ii) erfüllen. Falls w durch Y → bY c abgeleitet wurde, muss demnach u ∈ {a∗ b∗ } und u0 ∈ {c∗ } und #a (u) + #b (u) = #c (u) gelten. w erfüllt also (i) und (ii). Wenden wir darauf nun die Regeln Y → bY c oder Y → an, dann erhalten wir ubY bu0 , bzw. uu0 . Offensichtlich erfüllen beide Wörter (i) und(ii). "⊇": Als nächstes zeigen wir, dass L(G) ⊇ {an bm cn+m |n, m ∈ N }. Hierzu beweisen wir ∀n, m ∈ N : X ⇒∗G an bm cn+m per Induktion über n. Induktionsanfang: n = 0 m m m m X ⇒G Y ⇒m G b Y c ⇒G b c Induktionsannahme: ∀m ∈ N : X ⇒∗G an bm cn+m für festes n ∈ N Induktionsschritt: n 7→ n + 1 X ⇒G aXc ⇒∗G aan bm cn+m c = an+1 bm c(n+1)+m mithilfe der Induktionsannahme Insgesamt ergibt sich ∀n, m ∈ N : S ⇒G X ⇒∗G an bm cn+m . Aufgabe 5.2 (12 Punkte) Welche der folgenden Sprachen sind kontextfrei und welche nicht? Begründen Die Ihre Entscheidung, d.h. falls die Sprache nicht kontextfrei sein sollte, geben Sie einen Beweis dafür. Falls die Sprache kontextfrei ist, geben Sie eine kontextfreie Grammatik dafür an. Geben Sie in diesem Fall auch für ein mindestens 10 Zeichen langes Wort der Sprache eine Linksableitung und einen Ableitungsbaum an. (a) Die Sprache La bestehe aus korrekten Klammerausdrücken der 3 Klammertypen {}, [] und (), also liegen zum Beispiel {}()[] und ([]{}) in La , [{(})] jedoch nicht. (b) Lb = {ai bj ck |i, j, k ∈ N, i < j < k} (c) Lc = {uawb|u, w ∈ {a, b}∗, u und w gleich lang} Lösungsvorschlag 5.2 (a) Kontextfrei: Es ist folgendes G mit L(G) = La : G = ({{, }, (, ), [, ]}, {S, S 0 }, S 0 , P ) mit P = {S 0 → , S 0 → S, S → SS, S → {S}, S → [S], S → (S), S → } Das Wort [(()()){}] hat folgende Linksableitung: S 0 ⇒G S ⇒G [S] ⇒G [SS] ⇒G [(S)S] ⇒G [(SS)S] ⇒G [((S)S)S] ⇒G [(()S)S] ⇒G [(()(S))S] ⇒G [(()())S] ⇒G [(()()){S}] = [(()()){}] und folgenden Ableitungsbaum:
2/4
S’ S [
]
S S
S
) { S }
S
( S
S
( S ) ( S )
(b) Nicht kontextfrei: Es genügt zu zeigen, dass Lb keine NKA-Sprache ist. Beweis mit Pumping-Lemma für NKA-Sprachen: Sei N ∈ N beliebig. Sei z = aN bN +1 cN +2 und die Unterteilung z = uvwxy mit |vwx| ≤ N und |vx| > 0 beliebig. Fallunterscheidung: Fall 1: v oder x ist nicht Element {a}∗ ∪{b}∗ ∪{c}∗ , also besteht aus verschiedenen Zeichen. Durch aufpumpen mit i > 1 entsteht ein Wort, das nicht in der Sprache Lb liegt, da im Wort a’s nach b’s oder b’s nach c’s auftauchen. Fall 2: v enthält nur a’s. Dann kann x keine c’s enthalten. O.B.d.A nehmen wir an, dass x nur b’s enthält. Wir wählen i=3. Dann enthält das Wort uv i wxi y N + (i − 1) ∗ |v| = N + 2 ∗ |v| viele a’s aber weiterhin nur N + 2 ≤ N + 2 ∗ |v| c’s. Also ist uv i wxi y ∈ / Lb . Fall 3: x enthält nur c’s. Dann kann v keine a’s enthalten. O.B.d.A nehmen wir an, dass v nur b’s enthält. Wir wählen i=0. Dann ist uv i wxi y = uwy = aN bN +1−|v| cN +2−|x| . Da |vx| > 0, ist entweder #a (uwv) ≥ #b (uwv) oder #b (uwv) ≥ #c (uwv). Es ist also uwy ∈ / Lb . Lb ist also keine NKA-Sprache. (c) Kontextfrei: Für folgendes G gilt L(G) = Lc : G = ({a, b}, {S, X}, S, P ) mit P = {S → Xb, X → aXa, X → aXb, X → bxa, X → bXb, X → a} Das Wort abaaabbaab hat folgende Linksableitung: S ⇒G Xb ⇒G aXab ⇒G abXaab ⇒G abaXbaab ⇒G abaaXbbaab ⇒G abaaabbaab und folgenden Ableitungsbaum: S b
X a
a
X b
a
X a
X
b
a X b a
3/4
Aufgabe 5.3 (20 Punkte) Betrachten wir Automaten folgender Art: sie sind wie endliche Automaten außer, dass sie einen zweiten, unabhängigen Lesekopf für das Eingabeband besitzen. Beide Köpfe sind zu Beginn am linken Ende des Eingabebandes. Jeder der Leseköpfe kann in jedem Schritt unabhängig vom andere Kopf auf der gleichen Bandzelle verweilen oder um eine Zelle nach rechts rücken. Die Köpfe können nichts schreiben! Sie können auch nicht feststellen, ob sie sich gerade über der gleichen Bandzelle befinden. Was in jedem Rechenschritt passiert, wird vom derzeitigen Zustand und von den beiden von den Leseköpfen gelesenen Zeichen abhängen. (a) Geben Sie eine formale Definition so eines 2-Kopf-Automaten. (b) Definieren Sie formal, welche Worte von so einem Automaten akzeptiert werden. (Hinweis: Was sind hier die Konfigurationen?) (c) Wie verhält sich die Klasse der von diesen 2-Kopf-Automaten akzeptierten Sprachen zu den bis jetzt in der Vorlesung diskutierten Sprachklassen? Lösungsvorschlag 5.3 (a) Ein 2-NEA unterscheidet sich von einem NEA nur in der Übergangsrelation ∆: M = (Σ, Q, s, F, ∆) mit ∆ ⊆ Q × (Σ ∪ {ε}) × (Σ ∪ {ε}) × Q. Dabei steht (q, a, b, q 0 ) ∈ ∆ für einen Übergang vom Zustand q nach q 0 , wenn der erste Kopf a und der zweite b liest. (b) Wir gehen analog zu den endliche Automaten vor und definieren eine Konfiguration und eine darauf operierende Rechenschrittrelation. Konfiguration: (q, w, w0 ) mit q ∈ Q und w, w0 ∈ Σ∗ Endkonfigurationen: F in = {(f, ε, ε) | f ∈ F } Rechenschrittrelation: (q, aw, bw0 ) `M (q 0 , w, w0 ) :⇔ (q, a, b, q 0 ) ∈ ∆, hierbei kann a oder b auch ε sein. Ein 2-NEA akzeptiert nun ein Wort w ∈ Σ∗ , falls ein f ∈ F existiert mit (s, w, w) `∗M (f, ε, ε). (c) Ein 2-NEA erkennt trivialerweise alle regulären Sprachen. Allerdings ist diese Sprachklasse unvergleichbar mit kontextfreien Sprachen. – Zum Einen erkennt ein 2-NEA nicht kontextfreie Sprachen, wie Labc = {an bn cn | n ∈ N}: (a, ε) (c, b) (b, a)
start
q0
(b, a)
q1
(c, b)
q2
(ε, c) – Zum Anderen erkennt ein 2-NEA keine Palindrome. Dazu muss er nämlich den Anfang eines Wortes mit dem Ende vergleichen. Da ein 2-NEA keinen Speicher besitzt, müsste er mit einem Kopf zum Ende laufen. Danach müsste er mit diesem Kopf nach links laufen. Dies ist allerdings nicht erlaubt.
4/4
