Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

KiMoRi

Zuhörer

  • "KiMoRi" started this thread

Posts: 2

Date of registration: Nov 7th 2002

1

Wednesday, February 12th 2003, 7:04pm

Inhalt der Theo.Inf.-Klausur WS2002/2003

Also für alle die es interessiert hier ein (kleiner, grober) Überblick die Themen der einzelnen Klausuraufgaben:
Hinweis: ERRARE HUMANUM EST. - Irren ist menschlich!
(w € L steht für w ist Element von L, da das Zeichen nur als Kästchen  dargestellt wird)

1. Zeigen Sie, dass die Sprache L = { w € {a,b}* | |w|a und |w|b haben gleichen Rest bei Division durch 2} regulär ist.

2. Zeigen Sie, dass die Sprache L = {w € {a,b}* | |w|a = |w|b} nicht regulär ist.

3. Sei L eine reguläre Sprache über dem Alphabet ∑. Dann ist auch L¯ = ∑ L wieder regulär.

4. Zeigen Sie, dass die Sprache L = {aibiajbj | i,j >= 0} kontextfrei ist.

5. GOTO-Programm in WHILE-Programm:

1: IF x0 = 0 GOTO2;
     x1 := x1 +1;
    x0:=x0-x1;
    GOTO1;
2: x0:=x1;
    HALT

6. Multiple-Choice-Fragen:

 Jede kontextfreie Sprache ist entscheidbar.

 Jede Typ-0-Sprache ist entscheidbar.

 Jede entscheidbare Sprache ist vom Typ 0.

 Halteproblem K ist entscheidbar.

 Halteproblem ist rekursiv-aufzählbar.

 Das Komplement K¯ ist rekursiv-aufzählbar.

 Sei L regulär, dann gibt es eine Zahl n , sodass sich allle Wörter x € L mit |x|>= n zerlegen lassen in x = uvw , so dass folgende Eigenschaften erfüllt sind:
1. |v | >= 1,
2. |uv | <= n,
3. für alle i=0,1,2,... gilt: uvi w € L.

&#61488; Falls L regulär, dann gibt es eine Zahl n , sodass sich allle Wörter x € L mit |x|>= n zerlegen lassen in x = uvw , so dass folgende Eigenschaften erfüllt sind:
1. |v | >= 1,
2. |uv | <= n,
3. für alle i=0,1,2,... gilt: uvi w € L.

&#61488; Eine nicht-leere Menge L [Teilmenge] &#8721;* ist rekursiv-aufzählbar, g.d.w. es eine totale, berechenbare Funktion f:|N->&#8721;* gibt, so dass L mit dem Wertebereich von f übereinstimmt.

&#61488; Eine nicht-leere Menge L [Teilmenge] &#8721;* ist rekursiv-aufzählbar, g.d.w. es eine berechenbare Funktion f:|N->&#8721;* gibt, so dass L mit dem Wertebereich von f übereinstimmt.


bei eventuellen Fehler bitte daraufhinweisen, werde es dann ändern/berichtigen

habe jetzt "Zeigen Sie ..." hinzugefügt und die Macke mit dem backslash beseitigt
...S'Rioghal mo Dhream...
  • Send private message

mDev

Erfahrener Schreiberling

  • "mDev" is male

Posts: 282

Date of registration: Oct 10th 2002

Location: Hannover

Occupation: Wissenschaftlicher Mitarbeiter

2

Wednesday, February 12th 2003, 8:13pm

Quoted

1. Sprache L = { w € {a,b}* | |w|a und |w|b haben gleichen Rest bei Division durch 2} regulär?

2. Sprache L = {w € {a,b}* | |w|a = |w|b} nicht regulär?


es hiess jeweils "zeigen sie...", das is ein unterschied...

Quoted

3. Sei L eine reguläre Sprache über dem Alphabet &#8721;. Dann ist auch L¯ = &#8721; / L wieder regulär.


es war L¯ = &#8721;* &#92; L
(kann mir einer sagen warum hier kein backslash dargestellt wird?)
edit: hab den code eingegeben

Quoted

4. Sprache L = {aibiajbj | i,j >= 0} kontextfrei?


siehe 1 und 2
  • Send private message

smeyer82

Alter Hase

  • "smeyer82" is male

Posts: 372

Date of registration: Oct 14th 2002

Location: Ex-Kanzlerstadt Hannover

3

Wednesday, February 12th 2003, 8:57pm

Quoted


&#61488; Sei L regulär, dann gibt es eine Zahl n , sodass sich allle Wörter x € L mit |x|>= n zerlegen lassen in x = uvw , so dass folgende Eigenschaften erfüllt sind:
1. |v | >= 1,
2. |uv | <= n,
3. für alle i=0,1,2,... gilt: uvi w € L.

&#61488; Falls L regulär, dann gibt es eine Zahl n , sodass sich allle Wörter x € L mit |x|>= n zerlegen lassen in x = uvw , so dass folgende Eigenschaften erfüllt sind:
1. |v | >= 1,
2. |uv | <= n,
3. für alle i=0,1,2,... gilt: uvi w € L.


Der Unterschied war, dass beim ersten i>=0 und beim zweiten i>0 galt.
"Sir! We are surrounded!" - "Excellent! We can attack in any direction!"
  • Send private message

Joachim

Guru

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

4

Wednesday, February 12th 2003, 9:15pm

Quoted

Original von mDev
(kann mir einer sagen warum hierkein backslash dargestellt wird?)
Scheint ein Fehler in der Boardsoftware zu sein.

Wenn man aber einen doppelten Backslash eingibt, klappt es: \

Alternativ kann man das auch als numerische Zeichenreferenz codieren (&amp;#92;): &#92;
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message