Grundbegriffe der Informatik Tutorium 4 - Tutorium Nr. 32gbi.phil-opp.com/folien-ws2013/4.pdf · 2015. 11. 15. · Outline/Gliederung 1 Zum 3. Übungsblatt 2 Induktion über die Wortlänge

KARLSRUHER INSTITUT FÜR TECHNOLOGIE

Grundbegriffe der InformatikTutorium 4Tutorium Nr. 32

Philipp Oppermann | 21. November 2013

KIT – Universität des Landes Baden-Württemberg und

nationales Forschungszentrum in der Helmholtz-Gemeinschaft

www.kit.edu

http://www.kit.edu

Outline/Gliederung

1 Zum 3. Übungsblatt

2 Induktion über die Wortlänge

3 Kontextfreie Grammatiken

4 Aufgaben

5 Relationen

Zum 3. Übungsblatt Induktion über die Wortlänge Kontextfreie Grammatiken Aufgaben Relationen

Philipp Oppermann – GBI Tutorium Nr. 32 21. November 2013 2/13

Zum 3. Übungsblatt

Aufgabe 1hinreichend: X ⇒ L∗ endlich

notwendig: L∗endlich⇒ X

Gefordert war eine hinreichende und notwendige Bedingung!

Also X ⇐⇒ L∗ endlich

a) L = {} ∨ L = {ε}b) A ⊆ L



Zum 3. Übungsblatt





a) L = {} ∨ L = {ε}b) A ⊆ L



Zum 3. Übungsblatt





a) L = {} ∨ L = {ε}b) A ⊆ L



Zum 3. Übungsblatt





a) L = {} ∨ L = {ε}b) A ⊆ L



Zum 3. Übungsblatt





a) L = {} ∨ L = {ε}b) A ⊆ L



Zum 3. Übungsblatt





a) L = {} ∨ L = {ε}b) A ⊆ L



Zum 3. Übungsblatt

Aufgabe 2Wörter dürfen nur in Mengenklammern vorkommen!

{ab} a {b}∗ ist kein gültiger Audruck

Zusammenfassen nur mit runden Klammern!{{b} · {a}}∗ ist ungültig

{a, b}∗ = A∗, {a} ∪ {b} = {a, b}

Aufgabe 3

Angenommen ∃L : L+ = P. 2 ist prim =⇒ aa ∈ P = L+

=⇒ a ∈ L ∨ aa ∈ L =⇒ aaaa = a4 ∈ L+ =⇒ 4 ist prim E



Zum 3. Übungsblatt




{a, b}∗ = A∗, {a} ∪ {b} = {a, b}

Aufgabe 3





Zum 3. Übungsblatt




{a, b}∗ = A∗, {a} ∪ {b} = {a, b}

Aufgabe 3





Zum 3. Übungsblatt




{a, b}∗ = A∗, {a} ∪ {b} = {a, b}

Aufgabe 3





Zum 3. Übungsblatt




{a, b}∗ = A∗, {a} ∪ {b} = {a, b}

Aufgabe 3





Zum 3. Übungsblatt




{a, b}∗ = A∗, {a} ∪ {b} = {a, b}

Aufgabe 3





Zum 3. Übungsblatt




{a, b}∗ = A∗, {a} ∪ {b} = {a, b}

Aufgabe 3





Zum 3. Übungsblatt




{a, b}∗ = A∗, {a} ∪ {b} = {a, b}

Aufgabe 3





Zum 3. Übungsblatt

Aufgabe 4Induktionsanfang für n = 0

Für beliebiges aber festes n ∈ N0 gilt die Behauptung.

Induktionsschritt n y n + 1, IV verwenden

Aufgabe 5Der Induktionsanfang ist korrekt!

aber: der Induktionsschritt funktioniert nicht für 1 y 2



Zum 3. Übungsblatt








Zum 3. Übungsblatt








Zum 3. Übungsblatt








Zum 3. Übungsblatt








Vorkommen eines Zeichens

Definition

Nx(ε) = 0

∀y ∈ A : ∀w ∈ A∗ : Nx(yw) =

{1 + Nx(w) wenn y = x

Nx(w) wenn y 6= x

BeispielNa(abaab) = 1 + Na(baab) = 1 + Na(aab) = 1 + 1 + Na(ab) =1 + 1 + 1 + Na(b) = 1 + 1 + 1 + 0 = 3



Vorkommen eines Zeichens

Definition

Nx(ε) = 0

∀y ∈ A : ∀w ∈ A∗ : Nx(yw) =

{1 + Nx(w) wenn y = x

Nx(w) wenn y 6= x

BeispielNa(abaab) = 1 + Na(baab) = 1 + Na(aab) = 1 + 1 + Na(ab) =1 + 1 + 1 + Na(b) = 1 + 1 + 1 + 0 = 3



Induktion über die Wortlänge

Beweise, dass für alle w ∈ A∗ eine Aussage X gilt!

wie?∀w ∈ A∗ : X ⇐⇒ ∀n ∈ N0 ∀w ∈ An : XAlso:

IA: Zeige dass X für alle w ∈ A0 gilt (also für w = ε).IV: Für ein beliebiges aber festes n ∈ N0 gilt X für alle w ∈ An.IS: n y n + 1zz: X gilt ∀w ∈ An+1

∃u ∈ An und ∃v ∈ A mit uv = wIV verwenden, um zu zeigen dass X für uv wahr ist

Beispiele siehe Übung 4



































































Kontextfreie Grammatiken

DefinitionG = (N,T ,S,P)

N ist ein Alphabet von Nichtterminalsymbolen (Großbuchstaben)

T ist ein Alphabet von Terminalsymbolen (Kleinbuchstaben)

T ∩ N = ∅, V = T ∪ N

S ∈ N ist das Startsymbol

P ⊆ N × V ∗ ist eine endliche Menge von Produktionen

BeispielG = ({X ,Y} , {a, b} ,X ,P) mit P = {X → YY ,Y → aYb,Y → ε}

X ⇒ YY ⇒ aYbY ⇒ aaYbbY ⇒ aaYbbaYb ⇒ aaYbbaεb =aaYbbab ⇒ aaaYbbbab ⇒ aaaεbbbab = aaabbbab







T ∩ N = ∅, V = T ∪ N











T ∩ N = ∅, V = T ∪ N











T ∩ N = ∅, V = T ∪ N











T ∩ N = ∅, V = T ∪ N











T ∩ N = ∅, V = T ∪ N











T ∩ N = ∅, V = T ∪ N











T ∩ N = ∅, V = T ∪ N











T ∩ N = ∅, V = T ∪ N











T ∩ N = ∅, V = T ∪ N











T ∩ N = ∅, V = T ∪ N











T ∩ N = ∅, V = T ∪ N











T ∩ N = ∅, V = T ∪ N











T ∩ N = ∅, V = T ∪ N











T ∩ N = ∅, V = T ∪ N








Ableitungsschritt

(u ⇒ v)⇐⇒ ∃w1,w2 ∈ V ∗ und es existiert eine Produktion X → w in P,so dass u = w1Xw2 und v = w1ww2

Ableitung

u ⇒0 v ⇐⇒ u = v

∀i ∈ N0 : (u ⇒i+1 v ⇐⇒ ∃w ∈ V ∗ : u ⇒ w ⇒i v)

u ⇒∗ v ⇐⇒ ∃i ∈ N0 : u ⇒i v

BeispielG = ({X ,Y} , {a, b} ,X ,P) mit P = {X → YY ,Y → aYb | ε}

X ⇒4 aaYbbaYb ⇒∗ aaaεbbbab = aaabbbab, X ⇒∗ X ⇒∗ ab




Ableitungsschritt


Ableitung

u ⇒0 v ⇐⇒ u = v

∀i ∈ N0 : (u ⇒i+1 v ⇐⇒ ∃w ∈ V ∗ : u ⇒ w ⇒i v)

u ⇒∗ v ⇐⇒ ∃i ∈ N0 : u ⇒i v






Ableitungsschritt


Ableitung

u ⇒0 v ⇐⇒ u = v

∀i ∈ N0 : (u ⇒i+1 v ⇐⇒ ∃w ∈ V ∗ : u ⇒ w ⇒i v)

u ⇒∗ v ⇐⇒ ∃i ∈ N0 : u ⇒i v






Ableitungsschritt


Ableitung

u ⇒0 v ⇐⇒ u = v

∀i ∈ N0 : (u ⇒i+1 v ⇐⇒ ∃w ∈ V ∗ : u ⇒ w ⇒i v)

u ⇒∗ v ⇐⇒ ∃i ∈ N0 : u ⇒i v






Ableitungsschritt


Ableitung

u ⇒0 v ⇐⇒ u = v

∀i ∈ N0 : (u ⇒i+1 v ⇐⇒ ∃w ∈ V ∗ : u ⇒ w ⇒i v)

u ⇒∗ v ⇐⇒ ∃i ∈ N0 : u ⇒i v






Ableitungsschritt


Ableitung

u ⇒0 v ⇐⇒ u = v

∀i ∈ N0 : (u ⇒i+1 v ⇐⇒ ∃w ∈ V ∗ : u ⇒ w ⇒i v)

u ⇒∗ v ⇐⇒ ∃i ∈ N0 : u ⇒i v





Kontextfreie Sprache

DefinitionEine kontextfreie Sprache ist die von einer kontextfreien Grammatikerzeugte formale Sprache.

Ist G = (N,T ,S,P) dann ist L(G) = {w ∈ T ∗ | S ⇒∗ w}

Beispiel

G = ({X} , {a, b} ,X , {X → ε | aX | bX}) =⇒ L(G) =

{a, b}∗

L(G) = {} ⇐= G = ({X} , {a, b} ,X , {})G = ({X} , {(, )} ,X , {X → XX | (X) | ε})„wohlgeformte Klammerausdrücke“






Beispiel

G = ({X} , {a, b} ,X , {X → ε | aX | bX}) =⇒ L(G) =

{a, b}∗







Beispiel

G = ({X} , {a, b} ,X , {X → ε | aX | bX}) =⇒ L(G) =

{a, b}∗







Beispiel

G = ({X} , {a, b} ,X , {X → ε | aX | bX}) =⇒ L(G) = {a, b}∗







Beispiel


L(G) = {} ⇐= G =

({X} , {a, b} ,X , {})G = ({X} , {(, )} ,X , {X → XX | (X) | ε})„wohlgeformte Klammerausdrücke“






Beispiel


L(G) = {} ⇐= G = ({X} , {a, b} ,X , {})

G = ({X} , {(, )} ,X , {X → XX | (X) | ε})„wohlgeformte Klammerausdrücke“






Beispiel


L(G) = {} ⇐= G = ({X} , {a, b} ,X , {})G = ({X} , {(, )} ,X , {X → XX | (X) | ε})

„wohlgeformte Klammerausdrücke“






Beispiel






Aufgaben

Gib jeweils eine kontextfreie Grammatik über T = {a, b} an, die diefolgenden Sprachen erzeugt:

die Menge aller Wörter über T, in denen irgendwo das Teilwort baavorkommt

die Menge aller w ∈ T ∗ mit der Eigenschaft, dass für alle Präfixe vvon w gilt: |Na(v)− Nb(v)| ≤ 1

L ={

aibj | 0 ≤ i < j}



Relationen

Produkt von RelationenSind R ⊆ M1 ×M2 und S ⊆ M2 ×M3 zwei Relationen, dann heißtS ◦ R = {(x , z) ∈ M1 ×M3 | ∃y ∈ M2 : (x , y) ∈ R ∧ (y , z) ∈ S}das Produkt der Relationen R und S.

IdentitätIM = {(x , x) | x ∈ M}∀R ⊆ M ×M : R ◦ IM = R = IM ◦ R

Potenzen

R0 = IM

∀i ∈ N0 : R i + 1 = R ◦ R i

R∗ = ∪∞i=0R i „reflexiv-transitive Hülle “



Relationen



Potenzen

R0 = IM

∀i ∈ N0 : R i + 1 = R ◦ R i




Relationen



Potenzen

R0 = IM

∀i ∈ N0 : R i + 1 = R ◦ R i




Relationen

Potenzen

R0 = IM

∀i ∈ N0 : R i + 1 = R ◦ R i


reflexiv, symmetrisch, transitivEine Relation R über der Menge M heißt

reflexiv, wenn ∀x ∈ M : xRx .

symmetrisch, wenn ∀x , y ∈ M : xRy ⇐⇒ yRx

transitiv, wenn ∀x , y , z ∈ M : xRy ∧ yRz =⇒ xRz



Relationen

Potenzen

R0 = IM

∀i ∈ N0 : R i + 1 = R ◦ R i








Relationen

Potenzen

R0 = IM

∀i ∈ N0 : R i + 1 = R ◦ R i








Relationen

Potenzen

R0 = IM

∀i ∈ N0 : R i + 1 = R ◦ R i








Documents

Grundbegriffe der Informatik Tutorium 4 - Tutorium Nr. 32gbi.phil-opp.com/folien-ws2013/4.pdf · 2015. 11. 15. · Outline/Gliederung 1 Zum 3. Übungsblatt 2 Induktion über die Wortlänge