FreitagsrundenWiki - Benutzerbeiträge [de]

Lösungen TheGI TI Probeklausur vom 19.01.06

2006-02-12T16:25:11Z

Muellni: /* Aufgabe 17 */

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent Sebastian Bab war sich beim Vorrechnen manchmal selbst nicht sicher...
===Aufgabe 1===
:im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

===Aufgabe 2===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|a ∈ Σ
|Σⁱ = Σ
|ε ∉ Σ+
|ε ∈ Σ*
|-
|ø &sube; Σ+
|ø &sube; Σ*
|a ∈ Σ*
|{ε} ∉ Σ*
|-
|Σ² &sube; Σ*
|ø ∈ P(Σ*)
|{ε} ∈ P(Σ*)
|Σ² ∈ P(Σ*)
|}
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|{''aa,bb,ab,ba''} = Σ²
|{''xab'' : x ∈ Σ*} = {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|-
|{''ab,bb,aba''} &sube; Σ*
|{''axab'' : ''x'' ∈ Σ*} &sube; {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|}

===Aufgabe 3===
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' und endet mit ''b''}
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' oder ''b''}
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
# {''x'' ∈ Σ*; ''x'' beginnt nicht mit ''a''}
# {ø,{''a''},{''b''},{''a,b''}}
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}

===Aufgabe 4===
:''hier müßte man irgendwie Bilder hochladen können...''

===Aufgabe 5===

:a) ''L2'' = {''x'' ∈ Σ*; ''x'' beginnt mit ''ab''}
:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q3
|-
|q1
|q3
|q2
|-
|*q2
|q2
|q2
|-
|q3
|q3
|q3
|}
:c) einfach nur normale und Endzustände vertauschen:
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→*q0
|q1
|q3
|-
|*q1
|q3
|q2
|-
|q2
|q2
|q2
|-
|*q3
|q3
|q3
|}

===Aufgabe 6===
:a) ''L3'' = {''x'' ∈ Σ*; ''x'' = (anb)*am; n,m ≥ 1} ''dies ist meine Lösung. Über diese Aufgabe wurde lange diskutiert ohne dass etwas Vernünftiges heraus kam.''
:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
| -
|-
|*q1
|q1
|q0
|}
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeform werden muß. D.h. man muß einen Zustand q2 hinzufügen, der von q0 aus mit dem ''b'' erreicht wird. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

===Aufgabe 7===
:a) ''L4'' = {''x'' ∈ Σ*; ''x'' endet mit ''a''}
:b) ''bild einfügen''
:c)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|{q1,q0}
|{q0}
|-
|*q1
|ø
|ø
|}

===Aufgabe 8,9,10===
:''Lösungen werden in einer kommenden Vorlesung nachgereicht''

===Aufgabe 11===
:(Fortsetzung des Ansatzes) Da das Wort ''w'' mehr Zeichen enthält als der Automat Zustände hat, muß bei der Ableitung von ''w'' ein Zustand in A mindestens 2x besucht worden sein. Sei qs der erste Zustand in der Ableitung von ''w'', bei dem dies auftritt.
:Zerlege ''w'' wie folgt: ''w''=''xyz'' mit:
:*''x'' ist das Wort, welches bis zum ersten Auftreten von qs von A gelesen wird.
:*''y'' ist das Wort, welches vom Automaten in der Schleife von qs nach qs gelesen wird.
:*''z'' ist der Rest des Wortes ''w''.
: Es gelten die drei Eigenschaften des Pumping-Lemmas:
:#''y'' ≠ ε : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
:#''|xy|'' < ''n'' : gilt, da wir die erste Schleife in A gewählt haben.
:#''xy''k''z'' in ''L'' : Schleifen können mehrfach oder gar nicht abgearbeitet werden.

===Aufgabe 12===
:a) wähle n=5
:b) ''w''=abaaa ; ''x''=ab, ''y''=a, ''z''=aa; ''xy3z''=abaaaaa

===Aufgabe 13===
: (weiter nach Ansatz) Nach Definition des Pumping-Lemma läßt sich ''w'' in ''w''=xyz zerlegen. Nach Eigenschaft (2) des PL kann der Teil xy nur aus a's bestehen. y ist mindestens ein a. Nach (3) ist dann auch das Wort xy2z ∈ L. Für dieses Wort gilt aber xy2z = an-|y|a|y|+|y|an. Da n-|y|+|y|+|y| = n+|y| ≠ n gilt, stehen zu Beginn des Wortes mehr a's als am Ende → Widerspruch!

===Aufgabe 14===
:a) ''bilder...''
:b)
:#S⇒ ''a''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''
:#S⇒ ''a''S''b''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''

===Aufgabe 15===
:von oben nach unten
:*Typ-0; allgemeine
:*Typ-1; kontext-sensitive
:*Typ-2; kontext-freie
:*Typ-3; reguläre

===Aufgabe 16===
:''Lückentext'': Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik ''G'' ist ein Tupel ''G'' = (Σ,V,S,P), wobei Σ ein Alphabet, V eine Menge von Variablen, S die Startvariable und P eine Menge von Produktionsregeln ist.
:Die Klasse der regulären Sprachen enthält Sprachen, die über regulären Grammatiken gebildet werden können. Eine Grammatik heißt regulär, wenn alle ihre Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaften u ∈ V sowie ''v'' ∈ Σ oder ''v'' ∈ Σ ο V erfüllen. Ein Beispiel einer typischen regulären Sprache ist die Sprache ''Lrg'' = {an | n ≥ 1}. Reguläre Sprachen können entweder endlich oder unendlich sein. Die Klasse der endlichen Sprachen bildet hierbei eine Teilklasse der regulären Sprachen. Reguläre Sprachen werden von enlichen Automaten erkannt. Endliche Automaten können deterministisch oder nichtdeterministisch sein. Die Klasse der von deterministischen endlichen Automaten akzeptierten Sprachen ist hierbei gleich der Klasse der von nichtdeterministischen endlichen Automaten akzeptierten Sprachen.
:Die kontextfreien Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Form ''u'' ∈ V sowie ''v'' ∈ (Σ∪V)* haben. Damit ist natürlich jede reguläre Grammatik auch eine kontextfreie Grammatik. Ein typisches Beispiel einer kontextfreien Sprache ist ''Lkf'' = {anbn|n > 1} . Jede kontextfreie Grammatik ''G'' läßt sich durch geeignetes Umformen der Regeln der Grammatik in eine Grammatik ''G'' ' in Chomsky-Normalform konvertieren. Die von ''G'' und ''G'' ' erzeugten Sprachen sind hierbei gleich. Die Produktionsregeln ''u'' → ''v'' ∈ ''P'' von Grammatiken in Chomsky-Normalform sind hierbei von der Form ''u'' ∈ V und ''v'' ∈ Σ oder ''u'' ∈ V und ''v'' ∈ V ο V. Kontextfreie Sprachen werden von deterministsischen oder nichtdeterministischen Kellermaschinen erkannt. Die Klasse der don deterministischen Kellermaschinen akzeptierten Sprachen ist hierbei ungleich der Klasse der von nichtdeterministischen Kellerautomaten akzeptierten Sprachen. Palindrome sind Worte über einem Alphabet, die von vorne gelesen das selbe Wort ergeben wie von hinten gelesen. Die Sprache der Palindrome mit Trennzeichen läßt sich hierbei auch von deterministischen Kellermaschinen akzeptieren, wohingegen die Sprache der Palindrome ohne Trennzeichen nur von nichtdeterministischen Kellermaschinen akzeptiert wird.
:Die kontextsensitiven Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaft ''u'' ∈ (Σ∪V)*οVο(Σ∪V)* und ''v'' ∈ (Σ∪V)* mit |''u''| ≤ |''v''| erfüllen. Ein Beispiel einer typischen kontextsensitiven Sprache ist ''Lks'' = {anbncn| n ≥ 1}
: Die allgemeinen Sprachen werden ebenfalls über Grammatiken gebildet, wobei die Produktionsregeln dieser Grammatiken keinen Einschränkungen unterliegen. Ein typisches Beispiel einer allgemeinen Sprache ist das Halteproblem.

===Aufgabe 17===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!Schnitt
!Vereinigung
!Komplement
!Verkettung
!Stern
|-
|Typ 3
|ja
|ja
|ja
|ja
|ja
|-
|Det. kf
|nein
|nein
|ja
|ja
|ja
|-
|Typ 2
|nein
|ja
|nein
|ja
|ja
|-
|Typ 1
|ja
|ja
|ja
|ja
|ja
|-
|Typ 0
|ja
|ja
|nein
|ja
|ja
|}
:Quelle [http://www-fs.informatik.uni-tuebingen.de/skripte/info3.pdf für det.kf.] und [http://de.wikipedia.org/wiki/Chomsky-Hierarchie Restliche]

Lösungen TheGI TI Probeklausur vom 19.01.06

2006-02-12T16:24:36Z

Muellni: /* Aufgabe 17 */

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent Sebastian Bab war sich beim Vorrechnen manchmal selbst nicht sicher...
===Aufgabe 1===
:im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

===Aufgabe 2===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|a ∈ Σ
|Σⁱ = Σ
|ε ∉ Σ+
|ε ∈ Σ*
|-
|ø &sube; Σ+
|ø &sube; Σ*
|a ∈ Σ*
|{ε} ∉ Σ*
|-
|Σ² &sube; Σ*
|ø ∈ P(Σ*)
|{ε} ∈ P(Σ*)
|Σ² ∈ P(Σ*)
|}
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
|{''aa,bb,ab,ba''} = Σ²
|{''xab'' : x ∈ Σ*} = {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|-
|{''ab,bb,aba''} &sube; Σ*
|{''axab'' : ''x'' ∈ Σ*} &sube; {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|}

===Aufgabe 3===
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' und endet mit ''b''}
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' oder ''b''}
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
# {''x'' ∈ Σ*; ''x'' beginnt nicht mit ''a''}
# {ø,{''a''},{''b''},{''a,b''}}
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}

===Aufgabe 4===
:''hier müßte man irgendwie Bilder hochladen können...''

===Aufgabe 5===

:a) ''L2'' = {''x'' ∈ Σ*; ''x'' beginnt mit ''ab''}
:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
|q3
|-
|q1
|q3
|q2
|-
|*q2
|q2
|q2
|-
|q3
|q3
|q3
|}
:c) einfach nur normale und Endzustände vertauschen:
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→*q0
|q1
|q3
|-
|*q1
|q3
|q2
|-
|q2
|q2
|q2
|-
|*q3
|q3
|q3
|}

===Aufgabe 6===
:a) ''L3'' = {''x'' ∈ Σ*; ''x'' = (anb)*am; n,m ≥ 1} ''dies ist meine Lösung. Über diese Aufgabe wurde lange diskutiert ohne dass etwas Vernünftiges heraus kam.''
:b)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|q1
| -
|-
|*q1
|q1
|q0
|}
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeform werden muß. D.h. man muß einen Zustand q2 hinzufügen, der von q0 aus mit dem ''b'' erreicht wird. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

===Aufgabe 7===
:a) ''L4'' = {''x'' ∈ Σ*; ''x'' endet mit ''a''}
:b) ''bild einfügen''
:c)
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!a
!b
|-
|→q0
|{q1,q0}
|{q0}
|-
|*q1
|ø
|ø
|}

===Aufgabe 8,9,10===
:''Lösungen werden in einer kommenden Vorlesung nachgereicht''

===Aufgabe 11===
:(Fortsetzung des Ansatzes) Da das Wort ''w'' mehr Zeichen enthält als der Automat Zustände hat, muß bei der Ableitung von ''w'' ein Zustand in A mindestens 2x besucht worden sein. Sei qs der erste Zustand in der Ableitung von ''w'', bei dem dies auftritt.
:Zerlege ''w'' wie folgt: ''w''=''xyz'' mit:
:*''x'' ist das Wort, welches bis zum ersten Auftreten von qs von A gelesen wird.
:*''y'' ist das Wort, welches vom Automaten in der Schleife von qs nach qs gelesen wird.
:*''z'' ist der Rest des Wortes ''w''.
: Es gelten die drei Eigenschaften des Pumping-Lemmas:
:#''y'' ≠ ε : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
:#''|xy|'' < ''n'' : gilt, da wir die erste Schleife in A gewählt haben.
:#''xy''k''z'' in ''L'' : Schleifen können mehrfach oder gar nicht abgearbeitet werden.

===Aufgabe 12===
:a) wähle n=5
:b) ''w''=abaaa ; ''x''=ab, ''y''=a, ''z''=aa; ''xy3z''=abaaaaa

===Aufgabe 13===
: (weiter nach Ansatz) Nach Definition des Pumping-Lemma läßt sich ''w'' in ''w''=xyz zerlegen. Nach Eigenschaft (2) des PL kann der Teil xy nur aus a's bestehen. y ist mindestens ein a. Nach (3) ist dann auch das Wort xy2z ∈ L. Für dieses Wort gilt aber xy2z = an-|y|a|y|+|y|an. Da n-|y|+|y|+|y| = n+|y| ≠ n gilt, stehen zu Beginn des Wortes mehr a's als am Ende → Widerspruch!

===Aufgabe 14===
:a) ''bilder...''
:b)
:#S⇒ ''a''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''
:#S⇒ ''a''S''b''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''

===Aufgabe 15===
:von oben nach unten
:*Typ-0; allgemeine
:*Typ-1; kontext-sensitive
:*Typ-2; kontext-freie
:*Typ-3; reguläre

===Aufgabe 16===
:''Lückentext'': Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik ''G'' ist ein Tupel ''G'' = (Σ,V,S,P), wobei Σ ein Alphabet, V eine Menge von Variablen, S die Startvariable und P eine Menge von Produktionsregeln ist.
:Die Klasse der regulären Sprachen enthält Sprachen, die über regulären Grammatiken gebildet werden können. Eine Grammatik heißt regulär, wenn alle ihre Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaften u ∈ V sowie ''v'' ∈ Σ oder ''v'' ∈ Σ ο V erfüllen. Ein Beispiel einer typischen regulären Sprache ist die Sprache ''Lrg'' = {an | n ≥ 1}. Reguläre Sprachen können entweder endlich oder unendlich sein. Die Klasse der endlichen Sprachen bildet hierbei eine Teilklasse der regulären Sprachen. Reguläre Sprachen werden von enlichen Automaten erkannt. Endliche Automaten können deterministisch oder nichtdeterministisch sein. Die Klasse der von deterministischen endlichen Automaten akzeptierten Sprachen ist hierbei gleich der Klasse der von nichtdeterministischen endlichen Automaten akzeptierten Sprachen.
:Die kontextfreien Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Form ''u'' ∈ V sowie ''v'' ∈ (Σ∪V)* haben. Damit ist natürlich jede reguläre Grammatik auch eine kontextfreie Grammatik. Ein typisches Beispiel einer kontextfreien Sprache ist ''Lkf'' = {anbn|n > 1} . Jede kontextfreie Grammatik ''G'' läßt sich durch geeignetes Umformen der Regeln der Grammatik in eine Grammatik ''G'' ' in Chomsky-Normalform konvertieren. Die von ''G'' und ''G'' ' erzeugten Sprachen sind hierbei gleich. Die Produktionsregeln ''u'' → ''v'' ∈ ''P'' von Grammatiken in Chomsky-Normalform sind hierbei von der Form ''u'' ∈ V und ''v'' ∈ Σ oder ''u'' ∈ V und ''v'' ∈ V ο V. Kontextfreie Sprachen werden von deterministsischen oder nichtdeterministischen Kellermaschinen erkannt. Die Klasse der don deterministischen Kellermaschinen akzeptierten Sprachen ist hierbei ungleich der Klasse der von nichtdeterministischen Kellerautomaten akzeptierten Sprachen. Palindrome sind Worte über einem Alphabet, die von vorne gelesen das selbe Wort ergeben wie von hinten gelesen. Die Sprache der Palindrome mit Trennzeichen läßt sich hierbei auch von deterministischen Kellermaschinen akzeptieren, wohingegen die Sprache der Palindrome ohne Trennzeichen nur von nichtdeterministischen Kellermaschinen akzeptiert wird.
:Die kontextsensitiven Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaft ''u'' ∈ (Σ∪V)*οVο(Σ∪V)* und ''v'' ∈ (Σ∪V)* mit |''u''| ≤ |''v''| erfüllen. Ein Beispiel einer typischen kontextsensitiven Sprache ist ''Lks'' = {anbncn| n ≥ 1}
: Die allgemeinen Sprachen werden ebenfalls über Grammatiken gebildet, wobei die Produktionsregeln dieser Grammatiken keinen Einschränkungen unterliegen. Ein typisches Beispiel einer allgemeinen Sprache ist das Halteproblem.

===Aufgabe 17===
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
!
!Schnitt
!Vereinigung
!Komplement
!Verkettung
!Stern
|-
|Typ 3
|ja
|ja
|ja
|ja
|ja
|-
|Det. kf
|nein
|nein
|ja
|ja
|ja
|-
|Typ 2
|nein
|ja
|nein
|ja
|ja
|-
|Typ 1
|ja
|ja
|ja
|ja
|ja
|-
|Typ 0
|ja
|ja
|nein
|ja
|ja
|}

Quelle [http://www-fs.informatik.uni-tuebingen.de/skripte/info3.pdf für det.kf.] und [http://de.wikipedia.org/wiki/Chomsky-Hierarchie Restliche]

2006-01-22T15:10:42Z

Muellni: /* Aufgabe 16 */

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent (Sebastian Bab?) war sich beim Vorrechnen oft selbst nicht sicher...
===Aufgabe 1===
:im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

===Aufgabe 2===
:{| border="1"
|a ∈ Σ
|Σⁱ = Σ
|ε ∉ Σ+
|ε ∈ Σ*
|-
|ø &sube; Σ+
|ø &sube; Σ*
|a ∈ Σ*
|{ε} ∉ Σ*
|-
|Σ² &sube; Σ*
|ø ∈ P(Σ*)
|{ε} ∈ P(Σ*)
|Σ² ∈ P(Σ*)
|}
:{| border="1"
|{''aa,bb,ab,ba''} = Σ²
|{''xab'' : x ∈ Σ*} = {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|-
|{''ab,bb,aba''} &sube; Σ*
|{''axab'' : ''x'' ∈ Σ*} &sube; {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|}

===Aufgabe 3===
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' und endet mit ''b''}
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' oder ''b''}
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
# {''x'' ∈ Σ*; ''x'' beginnt nicht mit ''a''}
# {ø,{''a''},{''b''},{''a,b''}}
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}

===Aufgabe 4===
:''hier müßte man irgendwie Bilder hochladen können...''

===Aufgabe 5===

:a) ''L2'' = {''x'' ∈ Σ*; ''x'' beginnt mit ''ab''}
:b)
::{| border="1"
!
!a
!b
|-
|→q0
|q1
|q3
|-
|q1
|q3
|q2
|-
|*q2
|q2
|q2
|-
|q3
|q3
|q3
|}
:c) einfach nur normale und Endzustände vertauschen

===Aufgabe 6===
:a) ''L3'' = {''x'' ∈ Σ*; ''x'' = (anb)*am; n,m ≥ 1} ''dies ist meine Lösung. Über diese Aufgabe wurde lange diskutiert ohne dass etwas Vernünftiges heraus kam.''
:b)
::{| border="1"
!
!a
!b
|-
|→q0
|q1
| -
|-
|*q1
|q1
|q0
|}
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeform werden muß. D.h. man muß einen Zustand q2 hinzufügen, der von q0 aus mit dem ''b'' erreicht wird. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

===Aufgabe 7===
:a) ''L4'' = {''x'' ∈ Σ*; ''x'' endet mit ''a''}
:b) ''bild einfügen''
:c)
::{| border="1"
!
!a
!b
|-
|→q0
|{q1,q0}
|{q0}
|-
|*q1
|ø
|ø
|}

===Aufgabe 8,9,10===
:''Lösungen werden in einer kommenden Vorlesung nachgereicht''

===Aufgabe 11===
:(Fortsetzung des Ansatzes) Da das Wort ''w'' mehr Zeichen enthält als der Automat Zustände hat, muß bei der Ableitung von ''w'' ein Zustand in A mindestens 2x besucht worden sein. Sei qs der erste Zustand in der Ableitung von ''w'', bei dem dies auftritt.
:Zerlege ''w'' wie folgt: ''w''=''xyz'' mit:
:*''x'' ist das Wort, welches bis zum ersten Auftreten von qs von A gelesen wird.
:*''y'' ist das Wort, welches vom Automaten in der Schleife von qs nach qs gelesen wird.
:*''z'' ist der Rest des Wortes ''w''.
: Es gelten die drei Eigenschaften des Pumping-Lemmas:
:#''y'' ≠ ε : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
:#''|xy|'' < ''n'' : gilt, da wir die erste Schleife in A gewählt haben.
:#''xy''k''z'' in ''L'' : Schleifen können mehrfach oder gar nicht abgearbeitet werden.

===Aufgabe 12===
:a) wähle n=5
:b) ''w''=abaaa ; ''x''=ab, ''y''=a, ''z''=aa; ''xy3z''=abaaaaa

===Aufgabe 13===
: (weiter nach Ansatz) Nach Definition des Pumping-Lemma läßt sich ''w'' in ''w''=xyz zerlegen. Nach Eigenschaft (2) des PL kann der Teil xy nur aus a's bestehen. y ist mindestens ein a. Nach (3) ist dann auch das Wort xy2z ∈ L. Für dieses Wort gilt aber xy2z = an-|y|a|y|+|y|an. Da n-|y|+|y|+|y| = n+|y| ≠ n gilt, stehen zu Beginn des Wortes mehr a's als am Ende → Widerspruch!

===Aufgabe 14===
:a) ''bilder...''
:b)
:#S⇒ ''a''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''
:#S⇒ ''a''S''b''S⇒ ''aa''S''b''S⇒ ''aaa''S''b''S''b''S⇒ ''aaab''S''b''S⇒ ''aaabb''S⇒ ''aaabb''

===Aufgabe 15===
:von oben nach unten
:*Typ-0; allgemeine
:*Typ-1; kontext-sensitive
:*Typ-2; kontext-freie
:*Typ-3; reguläre

===Aufgabe 16===
:''Lückentext'': Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik ''G'' ist ein Tupel ''G'' = (Σ,V,S,P), wobei Σ ein Alphabet, V eine Menge von Variablen, S die Startvariable und P eine Menge von Produktionsregeln ist.
:Die Klasse der regulären Sprachen enthält Sprachen, die über ... Grammatiken gebildet werden können. Eine Grammatik heißt ..., wenn alle ihre Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Eigenschaften u ∈ V sowie ''v'' ∈ Σ oder ''v'' ∈ Σ ο V erfüllen. Ein Beispiel einer typischen regulären Sprache ist die Sprache ''Lrg'' = {an | n > 1}. Reguläre Sprachen können entweder endlich oder unendlich sein. Die Klasse der endlichen Sprachen bildet hierbei eine Teilklasse der regulären Sprachen. Reguläre Sprachen werden von enlichen Automaten erkannt. Endliche Automaten können deterministisch oder nichtdeterministisch sein. Die Klasse der von deterministischen endlichen Automaten akzeptierten Sprachen ist hierbei gleich der Klasse der von nichtdeterministischen endlichen Automaten akzeptierten Sprachen.
:Die kontextfreien Sprachen werden durch dolche Grammatiken gebildet, deren Produktionsregeln ''u'' → ''v'' ∈ ''P'' die Form ''u'' ∈ V sowie ''v'' ∈ (Σ∪V)* haben. Damit ist natürlich jede reguläre Grammatik auch eine kontextfreie Grammatik.
:Ein typisches Beispiel einer kontextfreien Sprache ist ''Lkf'' = {anbn|n > 1} . Jede kontextfreie Grammatik ''G'' läßt sich durch geeignetes Umformen der Regeln der Grammatik in eine Grammatik ''G'' ' in Chomsky-Normalform konvertieren. Die von ''G'' und ''G'' ' erzeugten Sprachen sind hierebi gleich. Die Produktionsregeln ''u'' → ''v'' ∈ ''P'' von Grammatiken in Chomsky-Normalform sind hierbei von der Form ''u'' ∈ V und ''v'' ∈ Σ oder ''u'' ∈ V und''v'' ∈ V ο V. Kontextfreie Sprachen werden von

===Aufgabe 17===

Lösungen TheGI TI Probeklausur vom 19.01.06

Lösungen TheGI TI Probeklausur vom 19.01.06

2006-01-22T14:23:42Z

Muellni: /* Aufgabe 1 */

Lösungen TheGI TI Probeklausur vom 19.01.06

2006-01-22T14:23:34Z

Muellni: /* Aufgabe 2 */

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent (Sebastian Bab?) war sich beim Vorrechnen oft selbst nicht sicher...
===Aufgabe 1===
im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

===Aufgabe 2===
:{| border="1"
|a ∈ Σ
|Σⁱ = Σ
|ε ∉ Σ+
|ε ∈ Σ*
|-
|ø &sube; Σ+
|ø &sube; Σ*
|a ∈ Σ*
|{ε} ∉ Σ*
|-
|Σ² &sube; Σ*
|ø ∈ P(Σ*)
|{ε} ∈ P(Σ*)
|Σ² ∈ P(Σ*)
|}
:{| border="1"
|{''aa,bb,ab,ba''} = Σ²
|{''xab'' : x ∈ Σ*} = {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|-
|{''ab,bb,aba''} &sube; Σ*
|{''axab'' : ''x'' ∈ Σ*} &sube; {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|}

===Aufgabe 3===
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' und endet mit ''b''}
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' oder ''b''}
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
# {''x'' ∈ Σ*; ''x'' beginnt nicht mit ''a''}
# {ø,{''a''},{''b''},{''a,b''}}
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}

===Aufgabe 4===
:''hier müßte man irgendwie Bilder hochladen können...''

===Aufgabe 5===

:a) ''L2'' = {''x'' ∈ Σ*; ''x'' beginnt mit ''ab''}
:b)
::{| border="1"
!
!a
!b
|-
|→q0
|q1
|q3
|-
|q1
|q3
|q2
|-
|*q2
|q2
|q2
|-
|q3
|q3
|q3
|}
:c) einfach nur normale und Endzustände vertauschen

===Aufgabe 6===
:a) ''L3'' = {''x'' ∈ Σ*; ''x'' = (anb)*am; n,m ≥ 1} ''über diese Lösung wurde lange diskutiert''
:b)
::{| border="1"
!
!a
!b
|-
|→q0
|q1
| -
|-
|*q1
|q1
|q0
|}
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeform werden muß. D.h. man muß einen Zustand q2 hinzufügen, der von q0 aus mit dem ''b'' erreicht wird. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

===Aufgabe 7===
:a) ''L4'' = {''x'' ∈ Σ*; ''x'' endet mit ''a''}
:b) ''bild einfügen''
:c)
::{| border="1"
!
!a
!b
|-
|→q0
|{q1,q0}
|{q0}
|-
|*q1
|ø
|ø
|}

===Aufgabe 8,9,10===
''Lösungen werden in einer kommenden Vorlesung nachgereicht''

===Aufgabe 11===

Lösungen TheGI TI Probeklausur vom 19.01.06

2006-01-22T14:23:22Z

Muellni: /* Aufgabe 2 */

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent (Sebastian Bab?) war sich beim Vorrechnen oft selbst nicht sicher...
===Aufgabe 1===
im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

===Aufgabe 2===
:{| border="1"
|a ∈ Σ
|Σⁱ = Σ
|ε ∉ Σ+
|ε ∈ Σ*
|-
|ø &sube; Σ+
|ø &sube; Σ*
|a ∈ Σ*
|{ε} ∉ Σ*
|-
|Σ² &sube; Σ*
|ø ∈ P(Σ*)
|{ε} ∈ P(Σ*)
|Σ² ∈ P(Σ*)
|}
{| border="1"
|{''aa,bb,ab,ba''} = Σ²
|{''xab'' : x ∈ Σ*} = {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|-
|{''ab,bb,aba''} &sube; Σ*
|{''axab'' : ''x'' ∈ Σ*} &sube; {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|}

===Aufgabe 3===
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' und endet mit ''b''}
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' oder ''b''}
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
# {''x'' ∈ Σ*; ''x'' beginnt nicht mit ''a''}
# {ø,{''a''},{''b''},{''a,b''}}
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}

===Aufgabe 4===
:''hier müßte man irgendwie Bilder hochladen können...''

===Aufgabe 5===

:a) ''L2'' = {''x'' ∈ Σ*; ''x'' beginnt mit ''ab''}
:b)
::{| border="1"
!
!a
!b
|-
|→q0
|q1
|q3
|-
|q1
|q3
|q2
|-
|*q2
|q2
|q2
|-
|q3
|q3
|q3
|}
:c) einfach nur normale und Endzustände vertauschen

===Aufgabe 6===
:a) ''L3'' = {''x'' ∈ Σ*; ''x'' = (anb)*am; n,m ≥ 1} ''über diese Lösung wurde lange diskutiert''
:b)
::{| border="1"
!
!a
!b
|-
|→q0
|q1
| -
|-
|*q1
|q1
|q0
|}
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeform werden muß. D.h. man muß einen Zustand q2 hinzufügen, der von q0 aus mit dem ''b'' erreicht wird. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

===Aufgabe 7===
:a) ''L4'' = {''x'' ∈ Σ*; ''x'' endet mit ''a''}
:b) ''bild einfügen''
:c)
::{| border="1"
!
!a
!b
|-
|→q0
|{q1,q0}
|{q0}
|-
|*q1
|ø
|ø
|}

===Aufgabe 8,9,10===
''Lösungen werden in einer kommenden Vorlesung nachgereicht''

===Aufgabe 11===

Lösungen TheGI TI Probeklausur vom 19.01.06

2006-01-22T14:23:09Z

Muellni: /* Aufgabe 4 */

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent (Sebastian Bab?) war sich beim Vorrechnen oft selbst nicht sicher...
===Aufgabe 1===
im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

===Aufgabe 2===
{| border="1"
|a ∈ Σ
|Σⁱ = Σ
|ε ∉ Σ+
|ε ∈ Σ*
|-
|ø &sube; Σ+
|ø &sube; Σ*
|a ∈ Σ*
|{ε} ∉ Σ*
|-
|Σ² &sube; Σ*
|ø ∈ P(Σ*)
|{ε} ∈ P(Σ*)
|Σ² ∈ P(Σ*)
|}
{| border="1"
|{''aa,bb,ab,ba''} = Σ²
|{''xab'' : x ∈ Σ*} = {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|-
|{''ab,bb,aba''} &sube; Σ*
|{''axab'' : ''x'' ∈ Σ*} &sube; {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|}

===Aufgabe 3===
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' und endet mit ''b''}
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' oder ''b''}
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
# {''x'' ∈ Σ*; ''x'' beginnt nicht mit ''a''}
# {ø,{''a''},{''b''},{''a,b''}}
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}

===Aufgabe 4===
:''hier müßte man irgendwie Bilder hochladen können...''

===Aufgabe 5===

:a) ''L2'' = {''x'' ∈ Σ*; ''x'' beginnt mit ''ab''}
:b)
::{| border="1"
!
!a
!b
|-
|→q0
|q1
|q3
|-
|q1
|q3
|q2
|-
|*q2
|q2
|q2
|-
|q3
|q3
|q3
|}
:c) einfach nur normale und Endzustände vertauschen

===Aufgabe 6===
:a) ''L3'' = {''x'' ∈ Σ*; ''x'' = (anb)*am; n,m ≥ 1} ''über diese Lösung wurde lange diskutiert''
:b)
::{| border="1"
!
!a
!b
|-
|→q0
|q1
| -
|-
|*q1
|q1
|q0
|}
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeform werden muß. D.h. man muß einen Zustand q2 hinzufügen, der von q0 aus mit dem ''b'' erreicht wird. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

===Aufgabe 7===
:a) ''L4'' = {''x'' ∈ Σ*; ''x'' endet mit ''a''}
:b) ''bild einfügen''
:c)
::{| border="1"
!
!a
!b
|-
|→q0
|{q1,q0}
|{q0}
|-
|*q1
|ø
|ø
|}

===Aufgabe 8,9,10===
''Lösungen werden in einer kommenden Vorlesung nachgereicht''

===Aufgabe 11===

Technische Informatik

2006-01-22T14:21:20Z

Muellni: /* Links zu Lehrveranstaltungen im Hauptstudium */

Der Studiengang "Technische Informatik" soll einen Kompromiss zwischen den Studiengängen [[Informatik]] und [[Elektrotechnik]] darstellen. So besteht der Studienplan des Grundstudiums aus Fächern beider Studiengänge, wobei zunänchst nur die Lehrveranstaltungen [[Informatik A]] und [[Informatik B]] aus dem Gebiet der Informatik stammen und der Schwerpunkt bei Lehrveranstaltungen aus dem Grundstudium der Elektrotechnik liegt.

Eine Wahlmöglichkeit im [[Grundstudium]] ist nicht vorgesehen. Im Hauptstudium können jedoch Fächer aus Fachgebieten beider Studienrichtungen gewählt werden. Nähere Informationen sind im [http://iv.tu-berlin.de/teaching/TechInf/StudF/ti.pdf Studienführer] zu finden.

== Links zu Lehrveranstaltungen im Grundstudium ==

'''1. Semester'''
* [[Informatik 1]]
* [http://130.149.60.127/lehre/gde/index.html Grundlagen der Elektrotechnik I - Teil A]
* [http://www.moses.tu-berlin.de/Mathematik/ Moses - Höhere Mathematik für Ingenieure]
* [http://iapf.physik.tu-berlin.de/service_portal/et_ti_wi/index.php Physik für ET, TI und WI]

'''2. Semester'''
* [[Informatik 2]]
* Grundlagen der Elektrotechnik I - Teil B ([http://130.149.60.127/lehre/gde/index.html]?)
* [http://www.moses.tu-berlin.de/Mathematik/ Moses - Höhere Mathematik für Ingenieure]
* [http://iapf.physik.tu-berlin.de/service_portal/et_ti_wi/index.php Physik für ET, TI und WI]

'''3. Semester'''
* [[Informatik 3]]
* [http://rosw.cs.tu-berlin.de/lehre/leds/le1/ Logischer Entwurf digitaler Systeme 1]
* [http://www-tet.ee.tu-berlin.de/ Theoretische Elektrotechnik I]
* [http://mst.tu-berlin.de/becap/education/TI/709_710/709_710.htm Halbleiterbauelemente]
* [http://www.moses.tu-berlin.de/Mathematik/ Moses - Höhere Mathematik für Ingenieure]

'''4. Semester'''
* [[Informatik 4]]
* [http://rosw.cs.tu-berlin.de/lehre/leds/le2/ Logischer Entwurf digitaler Systeme 2]
* [http://mst.tu-berlin.de/becap/education/TI/707_708/707_708.htm Grundzüge der Elektronik]
* [http://ftsu01.nue.tu-berlin.de/ilias/login.php Signale und Systeme (ILIAS)]
* [http://www.moses.tu-berlin.de/Mathematik/ Moses - Höhere Mathematik für Ingenieure]

== Links zu Lehrveranstaltungen im Hauptstudium ==
'''5. Semester'''
* [[TheGI TI]]
* [http://rt.cs.tu-berlin.de/lehre/hwpti/index.html Hardware Praktikum]
* [http://pdv.cs.tu-berlin.de/MinMax-WS2004/ Praktikum Systemprogrammierung]

== Sonstige Links ==
'''Interessante Adressen'''
* http://iv.tu-berlin.de/ - Seiten der Fakultät IV
* http://www.tech-inf.de/ - Links, alte Klausuren und Lernhilfen rund um die Technische Informatik
* news:bln.lehre.tech-inf - Newsgroup zur Technischen Informatik (wird leider bisher kaum benutzt)

'''Wichtige Dokumente'''
* [http://iv.tu-berlin.de/teaching/TechInf/StudF/ti.pdf Studienführer Technische Informatik]
* [http://iv.tu-berlin.de/teaching/TechInf/StO.html Studienordnung Technische Informatik]
* [http://iv.tu-berlin.de/teaching/TechInf/PO.html Prüfungsordnung Technische Informatik]

[[Kategorie:Fakultäts-ABC]]

Lösungen TheGI TI Probeklausur vom 19.01.06

2006-01-22T14:20:06Z

Muellni: /* =Aufgabe 8,9,10 */

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent (Sebastian Bab?) war sich beim Vorrechnen oft selbst nicht sicher...
===Aufgabe 1===
im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

===Aufgabe 2===
{| border="1"
|a ∈ Σ
|Σⁱ = Σ
|ε ∉ Σ+
|ε ∈ Σ*
|-
|ø &sube; Σ+
|ø &sube; Σ*
|a ∈ Σ*
|{ε} ∉ Σ*
|-
|Σ² &sube; Σ*
|ø ∈ P(Σ*)
|{ε} ∈ P(Σ*)
|Σ² ∈ P(Σ*)
|}
{| border="1"
|{''aa,bb,ab,ba''} = Σ²
|{''xab'' : x ∈ Σ*} = {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|-
|{''ab,bb,aba''} &sube; Σ*
|{''axab'' : ''x'' ∈ Σ*} &sube; {''x'' ∈ Σ* : ''x'' endet mit ''ab''}
|}

===Aufgabe 3===
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' und endet mit ''b''}
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' oder ''b''}
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
# {''x'' ∈ Σ*; ''x'' beginnt nicht mit ''a''}
# {ø,{''a''},{''b''},{''a,b''}}
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}

===Aufgabe 4===
hier müßte man irgendwie Bilder hochladen können...

===Aufgabe 5===

:a) ''L2'' = {''x'' ∈ Σ*; ''x'' beginnt mit ''ab''}
:b)
::{| border="1"
!
!a
!b
|-
|→q0
|q1
|q3
|-
|q1
|q3
|q2
|-
|*q2
|q2
|q2
|-
|q3
|q3
|q3
|}
:c) einfach nur normale und Endzustände vertauschen

===Aufgabe 6===
:a) ''L3'' = {''x'' ∈ Σ*; ''x'' = (anb)*am; n,m ≥ 1} ''über diese Lösung wurde lange diskutiert''
:b)
::{| border="1"
!
!a
!b
|-
|→q0
|q1
| -
|-
|*q1
|q1
|q0
|}
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeform werden muß. D.h. man muß einen Zustand q2 hinzufügen, der von q0 aus mit dem ''b'' erreicht wird. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

===Aufgabe 7===
:a) ''L4'' = {''x'' ∈ Σ*; ''x'' endet mit ''a''}
:b) ''bild einfügen''
:c)
::{| border="1"
!
!a
!b
|-
|→q0
|{q1,q0}
|{q0}
|-
|*q1
|ø
|ø
|}

===Aufgabe 8,9,10===
''Lösungen werden in einer kommenden Vorlesung nachgereicht''

===Aufgabe 11===