ATFS Übung 1 – 26.4.2001

Matthias Hensler

15. August 2001

Aufgabe 1

1.a

∀ w ∈ Σ^{∗} : (w^{R})^{R}= w

Beweis mit vollständiger Induktion:

Induktionsanfang: (ε^{R})^{R}= ε

Induktionsschluß: (sei (w^{R})^{R}= w)

((wa)^{R})^{R}= (a(w^{R}))^{R}= (w^{R})^{R}a = wa _{□}

Beachte: ∀u,v ∈ Σ^{∗} : (uv)^{R}= v^{R}u^{R} (ab cd)^{R}:= (cd)^{R}(ab)^{R}

1.b

∀w ∈ Σ^{∗} (w^{R})^{n} = (w^{n})^{R}

Beweis mit vollständiger Induktion:

Induktionsanfgang: (w^{R})^{0} = ε = (w^{0})^{R}

Induktionsschluß: sei (w^{R})^{n} = (w^{n})^{R}

(w^{R})^{n+1} = w^{R}(w^{R})^{n} = w^{R}(w^{n})^{R}= (w^{n}w)^{R}= (w^{n+1} )^{R} _{□}

Aufgabe 2

2.a

∀L_{1},L_{2} ∈ Σ^{∗} : L_{1} ⊆ L_{2} ↷ L_{1}^{∗} ⊆ L_{2}^{∗}

↶ ↷ ∃n ∈ ℕ: w ∈ L_{1}^{n} ↶ ↷ ∃n_{1},...,n_{n} ∈ L_{1} : w = u_{1}...u_{n} ↶ ↷ ∃n_{1},...,n_{n} ∈ L_{2} : w = u_{1}...u_{n} ↶ ↷ ∃n ∈ ℕ: w ∈ L_{2}^{n} ↶ ↷ w ∈ L_{2}^{∗} _{□}

2.b

zu zeigen: L_{1}^{∗}∪ L_{2}^{∗} ⊆ (L_{1}∪ L_{2})^{∗}

L_{1} ⊆ L_{1}∪ L_{2} und L_{2} ⊆ L_{1}∪ L_{2}

↷^{a.)} L_{1}^{∗} ⊆ (L_{1}∪ L_{2})^{∗} und L_{2}^{∗} ⊆ (L_{1}∪ L_{2})^{∗}

↷ L_{1}^{∗}∪ L_{2}^{∗} ⊆ (L_{1}∪ L_{2})^{∗} _{□}

Aufgabe 3

3.a

α_{1} = (1 ∨ 01 ∨ 0011)^{∗}(0 ∨ Λ^{∗})

3.b

α_{2} = β_{1}∨ β_{2}

wobei β_{1} = (1 ∨ 01^{∗}0)^{∗} β_{2} = (0 ∨ 10^{∗}10^{∗}1)^{∗}

3.c

α_{3} = (01 ∨ 10)^{∗}

Aufgabe 4

Gegeben: α_{1},α_{2},α_{3} ∈ RegE Gesucht: β_{1},β_{2},β_{3}, so daß α_{i}β̃_{i}, i = 1,2,3 und sh(β_{i}) < sh(α_{i}), �α_{i}� = �β_{i}�

4.a

α_{1} = ((ab)^{∗}∨ (ba)^{∗})^{∗}
β_{1} = (ab ∨ ba)^{∗}

4.b

α_{2} = (a(b^{∗}c)^{∗})^{R}
β_{2} = Λ^{∗}∨ a(a ∨ b^{∗}c)^{∗}

4.c

α_{3} = ((abc)^{∗}ab)^{∗}
β_{3} = Λ^{∗}∨ ((abc ∨ ab)^{∗}ab)

geTEXt von Matthias Hensler

15. August 2001

Aufgabe 1

siehe Anhang

Q̂= \{\overline{δ}(ε\{q_{0}\},w)|w ∈ Σ^{∗}\}

δ̂(T,a) = \overline{δ}(T,a) = ε( ⋃_{q∈T}δ(q,a))

ε-Hülle von q_{0}: Der Zustand q_{0} sowie alle Zustände, die man durch ε-Transitionen von q_{0} aus erreichen kann.

Aufgabe 2

𝔄 =< Q,Σ,δ,q_{0},F >∈ NFA(ε)
𝔄^{P} =< Q̂,Σ,δ̂,q̂_{0},F̂ >∈ DFA(ε)

\overline{δ}: 𝔭(Q) × Σ^{∗} → 𝔭(Q)

⊆ \overline{δ̂}: Q̂× Σ^{∗} → Q̂

zu zeigen: ∀T ∈ Q̂,w ∈ Σ^{∗} \overline{δ̂}(T,w) = \overline{δ}(T,w).

Induktionsanfang: \overline{δ̂}(T,ε) = T = ε(T) = \overline{δ}(T,ε) Induktionsschluß: (sei \overline{δ̂}(T,w) = \overline{δ}(T,w))

\overline{δ̂}(T,wa) = δ̂(\overline{δ̂}(T,w),a) = \overline{δ}(\overline{δ̂}(T,w),a) =

(Beachte: \overline{δ}(T,wa) = ε( ⋃ _{q∈\overline{δ}(T,w)}δ(q,a)))

= ε( ⋃_{q∈\overline{δ}(\overline{δ̂}(T,w),ε)}δ(q,a)) =

= ε( ⋃_{q∈\overline{δ̂}(T,w)}δ(q,a)) =

= ε( ⋃_{q∈\overline{δ}(T,w)}δ(q,a)) = \overline{δ}(T,wa) □

Aufgabe 3

Für i = 1,2 sei 𝔄_{i} =< Q_{i},Σ,δ_{i},q_{0}^{i},F_{i} >∈ DFA(ε).

3.a

gesucht: 𝔄 ∈ DFA(ε) : L(𝔄) = L(𝔄_{1})L(𝔄_{2})

[figure: 𝔄′; ^{q_{0}^{1}}; ^{q_{0}^{2}}; 𝔄_{1}; 𝔄_{2}; ⊚; ⊚; ⊚; ε; ε]
𝔄 = 𝔄^{′P}
𝔄′=< Q,Σ,δ,q_{0},F >

Q = Q_{1}∪ Q_{2},q_{0} = q_{0}^{1},F = F_{2}

δ: Q × (ε ∨ {ε}) → 𝔭(Q)

δ(q,a) = \{ \begin{matrix}\{δ_{1}(q,a)\} & ,q ∈ Q_{1} \\ \{δ_{2}(q,a)\} & ,q ∈ Q_{2} \end{matrix}

δ(q,ε) = \{ \begin{matrix}∅ & ,q ∉ F_{1} \\ \{q_{0}^{2}\} & ,q ∈ F_{1} \end{matrix}

3.b

F = \{q ∈ Q|\overline{δ}(q,w) ∈ F_{1},w ∈ Σ^{∗}\}

Anhang: Folie zu Aufgabe 1 – erstellt vom Lehrstuhl

3

ATFS Übung 4 – 18.5.2001

geTEXt von Matthias Hensler (mh@wspse.de) 15. August 2001

Aufgabe 1

𝔄_{i} =< Q_{i},Σ,δ_{i},q_{0}^{i},F_{i} >∈ DFA(Σ)

1.a

𝔄^{∩} =< Q_{1}× Q_{2},Σ,δ,(q_{0}^{1},q_{0}^{2}),F >∈ DFA

δ\{ \begin{matrix}(Q_{1}× Q_{2}) × Σ → Q_{1}× Q_{2} \\ ((q_{1},q_{2}),a) ↦ (δ_{1}(q_{1},a),δ_{2}(q_{2},a)) \end{matrix}

F = F_{1}× F_{2}

1.b

F = (F_{1}× Q_{2}) ∪ (Q_{1}× F_{2})

Aufgabe 2

L ∈ ℒ (Σ_{1},DFA)

↷ ∃α ∈ RegE(Σ_{1}) : �α� = L ↷ ∃α ∈ RegE(Σ_{1}) : �h(α)� = h(L) ↷ h(L) ∈ ℒ (Σ_{2},DFA) ∀α ∈ RegE(Σ_{1}) h(�α�) = �h(α)� Induktionsanfang:

• h(�Λ�) = ∅ = �Λ� = �h(Λ)�

• h(�a�) = h({a}) = {h(a)} = �h(a)� Induktionsschluß: α,β

h(�α ∨ β�) = h(�α�∪ �β�)
= h(�α�) ∨ h(�β�)
= �h(α)�∪ �h(β)�
= �\underbrace{h(α) ∨ h(β)}�
= �h(α ∨ β)�

Aufgabe 3

L_{KL}sei die Menge der korrekten Klammerausdrücke. zu zeigen: |D(L_{KL})| = ∞ Definition: (w_{n})_{n∈ℕ},w_{n} ∈ {(,)}^{∗}, durch w_{n} = (^{n} ∀n ≠ m)^{n} ∈ d_{w_{n}}(L_{KL}) und )^{m} ∉ d_{w_{n}}(L_{KL}) ↷ ∀n ≠ m: d_{w_{n}}(L_{KL}) ≠ d_{w_{m}}(L_{KL}) ↷ |D(L_{KL})| = ∞ ↷ L_{KL}ist nicht regulär

geTEXt von Matthias Hensler (mh@wspse.de)

15. August 2001

π ∈ N × (ε ∪ N)^{∗} ⇒_{π}⊆ X^{∗}× X^{∗} ⇒_{G}:= ⋃ _{π∈P} ⇒_{π} w ∈ Σ^{∗} α_{1},...,α_{n} ∈ X^{∗} S = α_{1} ⇒_{G} α_{2} ⇒_{G} ... ⇒_{G} α_{n} = w

Aufgabe 1

siehe Folie im Netz

Aufgabe 2

2.a

G_{1} : S → bS|aSa|ε

2.b

G_{2} : S → aS|aSbb|aSbbb|ε

2.c

G_{3} : A →  aA|b
B →  bB|a
S →  AAS′BB
S′→ AS′B|ε

Aufgabe 3

3.a

Sei G =< N,Σ,P,S >∈ CFG(Σ) G^{R}=< N,Σ,P^{R},S >∈ CFG(Σ) P^{R}= {A → α^{R}|A → α ∈ P} Es gilt: L(G^{R}) = L(G)^{R}

3.b

G: S → aB|ε B → Sb L(G) = {a^{n}b^{n}|n ∈ ℕ} ∉ RegE({a,b})

geTEXt von Matthias Hensler (mh@wspse.de)

15. August 2001

Aufgabe 1

zu zeigen: ∀α ∈ X^{∗}NX^{∗},β_{1},β_{2} ∈ X^{∗} : S ⇒_{l}^{+} α ⇒_{l} β_{1}, α ⇒_{l} β_{2},β_{1} ≠ β_{2} ↷ ∄w ∈ Σ^{∗} : β_{1} ⇒^{∗} wundβ_{2} ⇒^{∗} w zeige zunächst: ∀α ∈ X^{∗}NX^{∗} : S ⇒_{l}^{+} α ↷ α ∈ �a^{∗}AbB� oder α ∈ �a^{∗}b(a ∨ b)^{∗}B�

Fall 1: α = a^{n}AbB ,n ∈ ℕ Unter Linksableitung ⇒_{l}: β_{1} = a^{n}aAbB, bzw. β_{2} = a^{n}bB

Fall 2: α = a^{n}bnB ,n ∈ ℕ,u ∈ {a,b}^{∗} Unter Linksableitung ⇒_{l}: a^{n}bnaB oder a^{n}bnbB, bzw. a^{n}bn

Aufgabe 2

L ∈ RegL(Σ) ↷ ∃𝔄 =< Q,Σ,δ,q_{0},F >∈ DFA(Σ) : L(𝔄) = L

Sei G =< Q,Σ,P,q_{0} >∈ CFG(Σ) : L(G) = L(𝔄) = L P = {q → ap|δ(q,a) = p} ∪ {q → ε|q ∈ F } zu zeigen: G ist eindeutig. Beweis: Angenommen, es existiert w ∈ Σ^{∗} und zwei Ableitungen:

A_{1} : q_{0} ⇒^{∗} α ⇒ β_{1} ⇒^{∗} w
A_{2} : q_{0} ⇒^{∗} α ⇒ β_{2} ⇒^{∗} w

(mit β_{1} ≠ β_{2})

q_{0} ⇒^{n} α ⇒ β ↷ α ∈ Σ^{n}Q

A_{1} : q_{0} ⇒^{∗} vq ⇒ vaq′⇒^{∗} w
A_{2} : q_{0} ⇒^{∗} vq ⇒ vaq′′⇒^{∗} w
q′= δ(q,a) = q′′

Dies ist ein Widerspruch. Es gibt also keine zwei Abbleitungen für dasselbe Wort, folglich ist die Grammatik eindeutig.

geTEXt von Matthias Hensler (mh@wspse.de)

15. August 2001

Aufgabe 1

zu zeigen: ℒ (Σ,PDA,F) = ℒ (Σ,PDA,ε) = ℒ (Σ,PDA,F,ε). Dazu genügt es zu zeigen:

1. ℒ (Σ,PDA,F) ⊆ ℒ (Σ,PDA,ε)

2. ℒ (Σ,PDA,ε) ⊆ ℒ (Σ,PDA,F,ε)

3. ℒ (Σ,PDA,F,ε) ⊆ ℒ (Σ,PDA,F)

denn: ”⊆“ transitiv und anti-symmetrisch.

1.a

sei L ∈ ℒ (Σ,PDA,F), zeige: L ∈ ℒ (Σ,PDA,ε). Klar ist: ∃𝔄 ∈ PDA(Σ) : L(𝔄,F) = L. zu zeigen: ∃𝔄 ∈ PDA(Σ) : L(𝔄,ε) = L. Sei 𝔄 =< Q,Σ,Γ,δ,q_{0},z_{0},F >, definiere 𝔄′=< Q′,Σ,Γ′,δ′,q′_{0},z′_{0}, ∅_{unbekannt, daεErkennung}> mit

Q′:= Q ∪ {q′_{0},q′_{f}}
Γ′:= Γ ∪ {z′_{0}}
δ′: Q′× Σ_{ε}× Γ′→ 𝔭_{f} (Q′× Γ^{′∗})

δ′(q,X,Z) := \{ \begin{matrix}δ(q,X,Z) ∪ \{(q′_{f},z)\} & fürq ∈ Q,X ∈ Σ_{ε},Z ∈ Γ \\ \{(q_{0},z_{0},z′_{0})\} & fürq = q′_{0},X = ε,Z = z′_{0} \\ \{(q′_{1},Z)\} & fürq ∈ F,Z ∈ Γ \\ \{(q′_{f},ε)\} & fürq = q′_{f},Z ∈ Γ′ \\ ∅ & sonst \end{matrix}

kurz : δ′= δ∪{q′_{0},ε,z′_{0}) → (q_{0},z_{0}z′_{0})}∪{(q,ε,Z) → (q_{f} ,Z)|q ∈ F,Z ∈ Gamma}∪{(q_{f} ,ε,Z) → (q_{f} ,ε)|Z ∈ Γ′}

w ∈ L(𝔄,F) ↶ ↷ ∃q ∈ F,α ∈ Γ^{∗} : (q_{0},w,z_{0}) ⊢_{𝔄}^{∗} (q,ε,α). Seien also q ∈ F,α ∈ Γ^{∗},h_{0},...,h_{n} ∈ Q × Σ^{∗} × Γ^{∗}

mit h_{0} = (q_{0},w,z_{0}) ⊢_{𝔄} h_{1} ⊢_{𝔄} ... ⊢_{𝔄} h_{n} = (q,ε,α) ↶ ↷ ∃h′_{0},...,h′_{n} ∈ Q × Σ^{∗}× (Γ^{∗}{z′_{0}}) h′_{0} = (q_{0},w,z_{0}z′_{0}) ⊢_{𝔄′}h′_{1} ⊢_{𝔄′}... ⊢_{𝔄′}h′_{n} = (q,ε,α,z′_{0}) “↶ ↷“ 𝔄′kann alle Transitionen von 𝔄,z′_{0} unten “↶ ↷“ keine der neuen Regeln anwendbar “↶ ↷“ (q′_{0},w,z′_{0}) ⊢_{𝔄′} (q_{0},w,z_{0}z′_{0}) ⊢_{𝔄′} ... ⊢_{𝔄′} (q,ε,αz′_{0}) ⊢_{𝔄′} (q′_{f},ε,αz′_{0}) ⊢_{𝔄′}^{|α|} (q_{f} ,ε,z′_{0}) ⊢_{𝔄′} (q_{f} ,ε,ε) ↶ ↷ w ∈ L(𝔄′,ε)

1.b

analog zu (a) konstruiere 𝔄′mit

δ′= δ ∪ {(q′_{0},ε,z_{0}) → (q_{0},z_{0}z′_{0})} ∪ {(q,ε,z′_{0}) → (q′_{f},ε)|q ∈ Q}
F′= {q′_{f}}

1.c

analog zu (a) konstruiere 𝔄′mit

δ′= δ ∪ {(q′_{0},ε,z_{0}) → (q_{0},z_{0}z′_{0})} ∪ {(q,ε,z′_{0}) → (q′_{f},z′_{0})|q ∈ F }
F′= {q′_{f}}

Aufgabe 2

2.a

𝔄_{G} =< Q,Σ,Γ,δ,q_{0},z_{0},F > mit Q := {Q},Σ := {a,b,c,d},Γ = Σ ∪ {S,A,B,C},q_{0} := q,z_{0} = S,F = ∅, sowie den Zustandsübergängen: δ(q,a,a) = {(q,ε)} = δ(q,b,b) = δ(q,c,c) = δ(q,d,d) und δ(q,X,Y) := ∅fürx ≠ y,δ(q,ε,S) := {(q,a,Sd),(q,A),(q,C)},δ(q,ε,A) := {(q,aAc),(q,B)},δ(q,ε,B) := {(q,bBc),(q,ε)},δ(q,ε,C) := {(q,bCd),(q,B)}

2.b

S ⇒ a\underline{S}d ⇒ a\underline{C}d ⇒ ab\underline{C}dd ⇒ ab\underline{B}dd ⇒ abb\underline{B}cdd ⇒ abbcdd (q,abbcdd,S) ⊢ (q,\overline{a}bbcdd,\overline{a}Sd) ⊢ (q,bbcdd,Sd) ⊢ (q,bbcdd,Cd) ⊢ (q,\overline{b}bcdd,\overline{b}Cdd) ⊢ (q,bcdd,Cdd) ⊢ (q,bcdd,Bdd) ⊢ (q,bcdd,bBcdd) ⊢ (q,cdd,Bcdd) → (q,cdd,cdd) ⊢ (q,ε)

Aufgabe 3

Definiere Γ^{≤n} := ⋃ _{i=0}^{n} Γ^{i}, dann gilt: {α ∈ Γ^{∗}|(q,w,z_{0}) ⊢^{∗} (q,u,α)} ⊆ Γ^{≤n}. Insbesondere: es existieren nur endlich viele α. Idee: kodiere diese in endlicher Kontrolle des endlichen Automaten (EA). Konstruiere EA 𝔄′_{i}=< Q′,Σ,δ′,q′_{0},F′_{i}> ,i = 1,2,...,n},Q′:= Q×Γ^{≤n} ,q′_{0} := (q_{0},z_{0}),δ′((q,z_{γ}),a) := {(q′,z_{m}...z_{1γ}) ∈ Q′×Γ^{∗}|(q′,z_{m}...z_{1}) ∈ δ(q,a,Z)}∩ Q′mit (a,z_{γ}) ∈ Q,a ∈ Σ_{ε} Endzustände: F_{1} := {(q,γ) ∈ Q′|q ∈ F },F_{2} := {(q,ε) ∈ Q′},F_{3} := {(q,ε) ∈ Q′|q ∈ F }

nach Konstruktion gilt: (q,uv,γ) ⊢^{∗} (q′,u,γ′),γ,γ′∈ Γ^{≤n} ↶ ↷(q′,γ′) ∈ \overline{δ}((q,γ),u), also L(𝔄_{1}) = L(𝔄,F),L(𝔄_{2}) = L(𝔄,ε),L(𝔄_{3}) = L(𝔄,F,ε)

geTEXt von Matthias Hensler (mh@wspse.de)

15. August 2001

Aufgabe 1

Angenommen es ex. 𝔄 < Q,Σ,Γ,δ,q_{0},Z_{0},F >∈ DPDA(Σ),so daß L(𝔄,Σ) die P-Eigenschaft (Prefix-Eigenschaft) nicht hat. Dann ex. u,v ∈ L(𝔄,Σ),u ≠ v,u ∈ Prf(v), d.h. a ∈ Σ,w ∈ Σ^{∗} : v = uaw.

Es gilt: (q_{0},u,Z_{0}) ⊢^{∗}_{𝔄} (q,ε,ε) für genau ein q ∈ Q.

Ferner: v ∈ L(𝔄,Σ) ↶ ↷ (q,aw,ε) ⊢^{+}_{𝔄} (q′,ε,ε),q′∈ Q (Widerspruch)

□

Aufgabe 2

Angenommen, L ∈ ℒ (Σ,DPDA),Σ = {a,b,c}. Dann gilt, daß das Komplement ebenfalls in der Sprache liegt: \overline{L}∈ ℒ (Σ,DPDA) ↷ \overline{L}∈ ℒ (Σ,PDA) ↷ \overline{L}∩ �a^{∗}b^{∗}c^{∗}� = \{a^{n}b^{n}c^{n}|n ∈ ℕ\} ∈ ℒ (Σ,PDA) (Widerspruch)

□

Abschlußeigenschaften von Sprachen sind stark Klausurrelevant!

Aufgabe 4

S → V := E | if E then S else S| if E then SA| begin SB end | repeat SB until E

E →V — true — false V →x|y|z A → LA|ε B →;SB|ε L → L

geTEXt von Matthias Hensler (mh@wspse.de) 15. August 2001

Aufgabe 1

1.a

G ist vom Typ 2, da P ⊆ N ×X^{∗}. G ist nicht vom Typ 3, da B → aD,C → Ca ∈ P (in Typ 3 dürfen entweder nur rechts- oder linkslineare Regeln vorkommen).

1.b

Sei die Typ 3-Grammatik G′gegeben wie folgt:

S → abB
B → C|aD
C → aC|ε
D → bD|ε

Es gilt offensichtlich L(G) = L(G′) und deshalb ist L(G) Typ 3 Sprache.

Aufgabe 2

2.a

Normierung von G:

1. G′: S → A_{a}SBC|ε A_{a}B → A_{a}A_{b} CB → BC A_{b}B → A_{b}A_{b} A_{b}C → A_{b}A_{c} A_{c}C → A_{c}A_{c} A_{a} → a A_{b} → b A_{c} → c

2. G′′: S → A_{a}SBC|ε A_{a}B → A_{a}A_{b}

\begin{matrix}CB → C′B \\ C′B → C′B′ \\ C′B′→ BB′ \\ BB′→ BC \end{matrix} \} CB → BC

⋮

2.b

• Σ = {a}

• Σ_{a} = {a,b,c}

• G_{1} : S′→ B_{a}S′|ε Ba → a normiert! L(G_{1}) = �a^{∗}�

• ϕ: 𝔭(Σ) → 𝔭(Σ_{a})

ϕ(a) = L(G′′)4

Konstruiere \overline{G}mit L(\overline{G}) = ϕ(L(G_{1})) = L(G′′)^{∗}:

\overline{G}: \overline{S}→ ĈS′|C → ε

\begin{matrix}S′→ B_{a}S′|ε \\ B_{a} → A′_{a} \end{matrix} \} P_{0}

ϕ → ĈA′_{a} → ĈS} P_{1}

\begin{matrix}Ĉ_{a}→ aĈ \\ Ĉ_{b}→ bĈ \\ Ĉ_{c}→ cĈ \end{matrix} \} P_{2}

S → A_{a}SBC} G′′

Aufgabe 3

3.a

Sei G =< N,Σ,P,S > vom Typ 0. Konstruiere G′=< N′,Σ,P′,S′> vom Typ 0, so daß L(G′) = {v|w ∈ L(G),v Permutation von w} wie folgt:

• N′= N · ∪{c_{1},c_{2},c_{3},S′}

• P′= P · ∪{S′→ c_{1}c_{2}Sc_{3}} · ∪{c_{2}a → ac_{2}|a ∈ Σ} · ∪{ac_{1} → c_{1}a|a ∈ Σ} · ∪{c_{1}a → ac_{1}|a ∈ Σ} · ∪{ac_{1}b → bc_{1}a|a,b ∈ Σ} · ∪{c_{1}c_{2}c_{3} → ε}

(Klausurrelevant! Auch Stern vom Typ 0 mit Kontrollsymbolen)

0.1 3.b

Keine Typ 1-Grammatik.

geTEXt von Matthias Hensler (mh@wspse.de)

15. August 2001

Aufgabe 1

Sei 𝔄 =< {q_{0},q_{1},...,q_{7},q_{f} },{a},{a,b,c,□},q_{0},□,{q_{f} },δ >∈ TM({a}).

q_{0}a q_{1}bR
q_{1}□ q_{f} □N
q_{1}a q_{2}aN
q_{2}a q_{2}aR
q_{2}□ q_{3}□L
q_{2}c q_{3}cL
q_{3}a q_{4}cL
q_{4}a q_{5}aL
q_{4}b q_{6}□R
q_{5}a q_{5}aL
q_{5}b q_{0}bR
q_{6}c q_{6}aR
q_{6}□ q_{7}□L
q_{7}a q_{7}aL
q_{7}□ q_{0}□R

Aufgabe 2

𝔄 =< Q,Σ,δ,q_{0},F >∈ DFA(Σ) Sei 𝔄′=< Q · ∪{q_{f} },Σ,Σ · ∪{□},q_{0},{q_{f} },δ′>∈ TM(Σ) gegeben durch:

δ′(q,a) = {(δ(q,a),a,R)}
δ′(q,□) = \{ \begin{matrix}\{(q_{f} ,□,R)\} & ,q ∈ F \\ ∅ & ,sonst \end{matrix}

Beweis: : a_{1}...a_{n} = w ∈ L(𝔄) ↶ ↷ \overline{δ}(q_{0},w) ∈ F ↶ ↷ ∃q_{1},...,q_{n−1} ∈ Q,q_{n} ∈ F : δ(q_{0},a_{1}) = q_{1},δ(q_{1},a_{2}) = q_{2},...,δ(q_{n−1} ,a_{n}) = q_{n}↶ ↷ ∃q_{1},...,q_{n−1} ∈ Q,q_{n} ∈ F : (q_{0},ε,a_{1},a_{2},...,a_{n}) ⊢ (q_{1},a_{1},a_{2},a_{3}...a_{n}) ⊢ ... ⊢ (q_{n−1} ,a_{1}...a_{n−1} ,a_{n},ε) ⊢ (q_{n},w,□,ε) ⊢ (q_{f} ,w□,□,ε) ↶ ↷ w ∈ L(𝔄′)

□

Aufgabe 3

Sei 𝔄 =< {q_{0},q_{f} },{$},{$,□},q_{0},□,{q_{f} },δ >∈ TM({$}) gegeben durch:

δ(q_{0},□) = {(q_{0},□,L),(q_{0},□,R)}
δ(q_{0},$) = {(q_{f} ,$,N)}
δ(q_{f} ,□) = δ(q_{f} ,$) = ∅

ATFS Übung 11 – 13.7.2001

geTEXt von Matthias Hensler (mh@wspse.de) 15. August 2001

Aufgabe 1

𝔄 =< {q_{0},q_{1},...,q_{5},q_{f} },{$},{$,□,|},q_{0},□,{q_{f} },δ >∈ 1 − dTM

gegeben wie folgt:

δ: Q × Γ −−→ Q × Γ × {L,N,R}
\begin{matrix}q_{0}$ & q_{f} $N \\ q_{0}□ & q_{1}|L \\ q_{1}$□ & q_{f} $N \\ q_{1}□ & q_{2}|R \end{matrix} \} ErzeugeRandmarkierungen

\begin{matrix}q_{2}□ & q_{2}□R \\ q_{2}| & q_{3}□R \\ q_{3}$ & q_{f} $N \\ q_{3}□ & q_{4}|L \end{matrix} \} GehezurechtemRandunderweitereihn

\begin{matrix}q_{4}□ & q_{4}□L \\ q4| & q_{5}□L \\ q_{5}$ & q_{f} $N \\ q_{5}□ & q_{2}|R \end{matrix} \} Gehenachlinks...

Aufgabe 2

2.a

Sei 𝔄 ∈ TM(Σ),∼⊆ \underline{Conf}(𝔄)ÃR definiert wie folgt:

(q,α,X,β) ∼ (q′,α′,X′,β′) : ↶ ↷

1. q = q′

2. X = X′

3. α = □^{n}α′oder α′= □^{n}α für n ∈ ℕ

4. β = β′□^{n} oder β′= β□^{n} für n ∈ ℕ

(q,□□ab,$,bc) ∼ (q,□ab,$,bc□)

Es gilt: ∀κ_{1},κ_{2},κ′_{1} ∈ \underline{Conf}(𝔄) : κ_{1} ⊢_{𝔄} κ_{2} und κ_{1} ∼ κ′_{1} ↷ ∃κ′_{2} ∼ κ_{2} : κ′_{1} ⊢ κ′_{2} Sei w ∈ L(𝔄). Dann gilt:

|\{[n]_{∼} |κ ∈ \underline{Conf}(𝔄),|κ| ≤ s(|w|)\}|
= |\{[n]_{∼} |κ ∈ \underline{Conf}(𝔄),|κ| = s(|w|)\}|
(∗) ≤ |Q| · s(|w|) · |Γ|

Es existiert γ = (κ_{0} = κ(w) ⊢ κ_{1} ⊢ ... ⊢ κ_{n}), κ_{n} Endkonfiguration mit: \underline{bv}(γ) ≤ s(|w|) und o.B.d.A. κ_{i}χκ_{j},i ≠ j (wegen (∗)n ≤ |Q|...)

2.b

Sei 𝔄 =< Q,Σ,Γ,q_{0},□,F,δ >∈ TM(Σ) linear beschränkt und p ∈ ℕ_{0}, so daß:

\underline{bv}_{𝔄}(w) ≤ p · |w| ∀w ∈ L(𝔄)\\{ε\}

Sei S: \{ \begin{matrix}ℕ → ℕ \\ n ↦ p · n \end{matrix}

Für alle w ∈ L(𝔄)\{ε} existiert Endkonfiguration κ und n ∈ ℕ, so daß n(w) ⊢_{𝔄}^{n} κ und n ≤ |Q|·p·|w|·|Γ|^{p·|w|}

2.c

Falls s eine berechenbare Funktion, dann ist L(𝔄) ∈ DEC(Σ). Für w ∈ Σ^{∗} berechne s(|w|) und untersuche die endlich vielen Berechnungen γ = (κ(w) ⊢ ...) der Länge |Q| · s(|w|) · |Γ| auf Endkonfigurationen.

1. Fall: Endkonfiguration vorhanden ⇝ w ∈ L(𝔄)

2. Fall: keine Endkonfiguration vorhanden ⇝ w ∉ L(𝔄)

geTEXt von Matthias Hensler (mh@wspse.de) 15. August 2001

Aufgabe 1

Seien α,β ∈ RegE:

1. Konstruiere 𝔄_{1},𝔄_{2} ∈ NFA: L(𝔄_{1}) = �α� und L(𝔄_{2}) = �β� (nach Thompson).

2. Konstruiere 𝔄′_{1},𝔄′_{2} ∈ DFA: L(𝔄′_{1}) = L(𝔄_{1}) und L(𝔄′_{2}) = L(𝔄_{2}) (Potenzmengenkonstruktion)

3. Konstruiere \overline{𝔄′_{1}},\overline{𝔄′_{2}} ∈ DFA: L(\overline{𝔄′_{1}}) = \overline{L(𝔄′_{1})}und L(\overline{𝔄′_{2}}) = \overline{L(𝔄′_{2})}.

4. Konstruiere 𝔄′_{1}× \overline{𝔄′_{2}},\overline{𝔄′_{1}}× 𝔄′_{2} : L(𝔄′_{1}× \overline{𝔄′_{2}} = L(𝔄′_{1}) ∩ L(\overline{𝔄′_{2}}) und L(\overline{𝔄′_{1}}) ∩ L(𝔄′_{2}).

5. Führe Leehrheitstes durch:

L(𝔄′_{1}× \overline{𝔄′_{2}}) =^{?} ∅

L(\overline{𝔄′_{1}}× 𝔄′_{2}) =^{?} ∅

6. �α� = �β�↶ ↷ Beide leer!

Aufabe 2

2.a

L_{r} = {a,b}^{∗}
L_{c} = {a^{n}b^{n}|n ∈ ℕ}

2.b

Falsch, denn: Angenommen \overline{L_{c}} = L_{r}. Dann gilt:

\overline{\overline{L_{c}}} = \overline{L_{r}} ↷ L_{c} = \overline{L_{r}}
↷ L_{c} ∈ RegL

Widerspruch!

Aufgabe 3

Sei 𝔄^{∩} =< Q_{1}× Q_{2},Σ,Γ,δ,(q_{0}^{1},q_{0}^{2}),Z_{0},F_{1}× F_{2} >∈ PDA(Σ).

δ: (Q_{1}× Q_{2}) × Σ_{Σ} × Γ → 𝔭_{f} ((Q_{1}× Q_{2}) × Γ^{∗}) ∀a ∈ Σ δ((q_{1},q_{2}),a,Z) = {((q,δ_{2}(q_{2},a)),β)|δ_{1}(q_{1},a,Z) ∋ (q,β)}

δ((q_{1},q_{2}),Σ,Z) = {((q_{1},q_{2}),β)|δ_{1}(q_{1},ε,Z) ∋ (q,β)}

L(𝔄^{∩},F,ε) = L(𝔄_{1},F,ε) ∩ L(𝔄_{2}).

Aufgabe 4

4.a (nicht Klausurrelevant)

L{ε,a}_{reg} ↷ L_{reg} Falsch, denn: ∀L ⊆ {a}^{∗} : {aa}∗ ⊆ L ↷ L{ε,a} = {a}^{∗} ∈ RegL({a}). Aber: ℒ = {L ⊆ {a}^{∗}|{aa}^{∗} ⊆ L} is überabzählbar. Da es nur abzählbar viele reguläre Sprachen gibt: ∃L ∈ ℒ : L ∉ RegL und L{ε,a} ∈ RegL({a})

4.b (Klausurrelevant)

Richtig, denn: L ∈ CFL↷ L\{ε} ∈ CFL

L ∈ CFL ↷ ∃G ∈ CNF: L(G) = L
↷ ∃G =< N,Σ,P,S >∈ CNF:
L(< N,Σ,P\{S → ε} >) = L\{ε}
↷ ∃G ∈ CNF: L(G) = L\{ε}
↷ ∃G ∈ CFG: L(g) = L\{ε}
↷ L\{ε} ∈ CFL

4.c

Falsch, denn: Seien L ∈ 𝔭(Σ^{∗})\ℒ_{0}(Σ) und f : ℕ → Σ^{∗}\L surjektiv. Seien ∀n ≥ 1 : L_{n} = Σ^{∗}\{f(n)} ∈ RegL. Es gilt: ⋂ _{n=1}^{∞} L_{n} = L.

ATFS Klausur-Übungen

geTEXt von Matthias Hensler (mh@wspse.de)

Übungen vom 29.6.2001 und 6.7.2001

15. August 2001

Aufgabe 1

Sei Σ Alphabet. Die Menge der ko-endlichen Sprachen ℒ := \{L ⊆ Σ^{∗}|\overline{L}: Σ^{∗}\L ist endlich \}.

1.a

Zeigen Sie: ℒ ist unter ∪,∩,^{∗} abgeschlossen.

1.b

In welchen Sprachklassen ist ℒ enthalten.

Lösung: 1.a

∪,∩: L_{1},L_{2} ∈ ℒ ↷ \overline{L_{1}},\overline{L_{2}}endlich
↷ \overline{L_{1}}∩ \overline{L_{2}},\overline{L_{1}}∪ \overline{L_{2}}endlich
↷ \overline{L_{1}∪ L_{2}},\overline{L_{1}∩ L_{2}}endlich
↷ L_{1}∪ L_{2},L_{1}∩ L_{2} ∈ ℒ

∗: L ∈ ℒ undL ⊆ L^{∗} ↷ L^{∗} ⊆ \overline{L}endlich
↷ L^{∗} ∈ ℒ

Lösung: 1.b

ℒ ⊆ RegL(Σ), denn L ∈ ℒ ↷ \overline{L}endlich ↷ \overline{L}regulär ↷ L regulär

Aufgabe 2

Sei Σ Alphabet und # ∉ Σ. Für L ⊆ Σ^{∗}: split(L) : {v#w|vw ∈ L}

2.a

Geben Sie split(L) für L = {a,bb,aba} explizit an.

2.b

Gegeben ist ein Automat 𝔄. Zu konstruieren ist ein Automat 𝔄′=split(𝔄).

Lösung: 2.a

split(L) = {#a,a#,#bb,b#b,bb#,#aba,a#ba,ab#a,aba#}

Lösung: 2.b

Wir kopieren den Automaten einfach, und von jedem Zustand des Originalautomaten einen Gatter-Über-gang (#) in den entsprechenden Zustand des Kopierautomaten. Der Endzustand des Originalautomaten ist hier kein Endzustand mehr. Damit wir einen deterministischen Automaten erhalten, fügen wir von jedem Zustand im kopierten Automaten noch eine Gatter-Senke in einen neuen Zustand ein, sowie eine Schleife mit a,b,# die wieder in die Senke führt. Der Originalautomat erzeugt das Prefix, und der kopierte das Suffix.

Aufgabe 3

Für L ⊆ Σ^{∗} und Σ^{∗} ⊆ Σ. sub(L) := {w ∈ L|w ∈ (Σ′)^{∗}} Beweisen oder widerlegen Sie:

3.a

L regulär ↷ sub(L) regulär.

3.b

sub(L) regulär ↷ L regulär.

Lösung: 3.a

Sei L ⊆ Σ^{∗} regulär. Dann existiert 𝔄 =< Q,Σ,δ,q_{0},F >∈ DFA(Σ), so daß L(𝔄) = L

Sei 𝔄′=< Q · ∪{q_{neu}},Σ,δ′,q_{0},F >∈ DFA(Σ) gegeben gemäß:

δ′(q,a) = \{ \begin{matrix}δ(q,a) & ,fallsa ∈ Σ′,q ∈ Q \\ q_{neu} & a ∈ Σ\Σ′oderq = q_{neu} \end{matrix}

Es gilt: L(𝔄′|sub(L(𝔄)) =sub(L) ↷sub(L) regulär.

Lösung: 3.b

Σ = {a,b,c},Σ′= {c} L = {a^{n}b^{n}|n ∈ ℕ} ∪ {c} ist nicht regulär, aber sub(L) = {c} regulär: Widerspruch.

Aufgabe 4

Beweisen oder widerlegen Sie:

4.a

L_{1} = {uavb|u,v ∈ {a,b}^{∗},|u| = |v|} ∈ CFL({a,b})

4.b

L_{2} = {a^{n}b^{n}c^{i}|i ≤ n} ∈ CFL({a,b,c})

Lösung: 4.a

S → Ab
A → aAa|aAb|bAa|bAb|a
L(G) = L_{1}

Lösung: 4.b

L_{2} ∉ CFL. Angenommen L_{2} sei kontextfrei. Dann ex. k ≥ 1 mit den Eigenschaften des Pumping-Lemmas. Sei z = a^{k}b^{k}c^{k} ∈ L_{2} und uvwxy Zerlegung von z gemäß Pumpinglemma.

1. Fall: vwx ∈ �a^{∗}b^{∗}� : uwy = a^{i}b^{j}c^{k} mit i < k oder j < k: Widerspruch!

2. Fall: vwx ∈ �b^{∗}c^{∗}� : uwy = a^{k}b^{i}c^{j} mit i < k oder j < k: Widerspruch! (Pumpinglemma stark Klausurrelevant!)