GTI - Klausurfrage-Stunde - Grundlagen der Informatik - Fachrat Informatik

Nagezahn

Junior Schreiberling

Posts: 198

Date of registration: Feb 9th 2010

Location: Nordstadt

1

Thursday, February 24th 2011, 12:43pm

GTI - Klausurfrage-Stunde

Hallo Leute,

kann mir jemand sagen, ob bei der gestrigen Klausurfragestunde außer Verständnisfragen andere Dinge besprochen wurden, die evtl. für die Klausur relevant sind? Wäre sehr nett!

MfG

Go to the top of the page

epix

Junior Schreiberling

Posts: 191

Date of registration: Sep 28th 2009

Location: Hannover

2

Thursday, February 24th 2011, 12:50pm

Moin, ich kann ja mal zusammenfassen was ich mir aufgeschrieben habe.

- Kurzfragenteil pflicht
- Auswahl 3 von 4 Fragen beantworten

Mögliche Themen:

- 1 Pumping Lemma Aufgabe
- 1 Aufgabe zu Entscheidbarkeit / Berechenbarkeit
- 1 Aufgabe zeigen von regulär / kontextfrei
- 1 Aufgabe While / Loop / Goto

Hilfsmittel: Beidseitig bedruckt / beschriebener DinA4 Zettel
Orientieren an der lezten Klausur (StudIp)

Gemacht haben wir dann noch ein Beispiel zum Satz von Rice und ein paar Beispiele aus den Übungsaugaben zu Loop.

Viele Grüße,
Jan

Go to the top of the page

cartman

Junior Schreiberling

Posts: 154

Date of registration: Mar 10th 2009

Location: Laatzen

3

Thursday, February 24th 2011, 2:29pm

In der Klausur aus dem WS09 ist folgende Aufgabe :
Beweisen oder widerlegen Sie: Die Sprache

L:= {xy | x,y € {0,1}*, |x|=|y| und |x|_1 + |y|_0 = |x| = |y|}

ist regulär.

Könnte mir jemand evtl. die Bedinungen für die Sprache erläutern, |x|=|y| verstehe ich ja, aber was soll dann der Rest, also |x|index1 + |y|index0 = |x|=|y| bedeuten, irgendwie erkenne ich das nicht.

Go to the top of the page

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

4

Thursday, February 24th 2011, 2:37pm

Quoted from "cartman"

In der Klausur aus dem WS09 ist folgende Aufgabe :
Beweisen oder widerlegen Sie: Die Sprache

L:= {xy | x,y € {0,1}*, |x|=|y| und |x|_1 + |y|_0 = |x| = |y|}

ist regulär.

Könnte mir jemand evtl. die Bedinungen für die Sprache erläutern, |x|=|y| verstehe ich ja, aber was soll dann der Rest, also |x|index1 + |y|index0 = |x|=|y| bedeuten, irgendwie erkenne ich das nicht.

L ist die Menge aller Wörter, die man (gleichmäßig) halbieren kann, sodass die Summe der 1en in der ersten Worthälfte plus die Summe der 0en in der zweiten Worthälfte genau die Hälfte der Gesamtwortlänge ergibt. Beispielsweise 10110111, 11, 00 gehören zu L, aber nicht 10, 01, 110000, sowie alle ungeraden Wortlängen gehören auch nicht zu L.

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Go to the top of the page

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

5

Thursday, February 24th 2011, 3:59pm

Quoted from "epix"

...
- 1 Aufgabe While / Loop / Goto

Hilfsmittel: Beidseitig bedruckt / beschriebener DinA4 Zettel
...

Dazu gab's noch den Hinweis, sich ggf. die (Unter-)Programme aus den Übungen auf dem Zettel zu notieren, falls die Aufgabenstellung auf elementare Befehle beschränkt ist.

This post has been edited 1 times, last edit by "Bastian" (Feb 24th 2011, 4:00pm)

Go to the top of the page

newgame

Trainee

Posts: 45

Date of registration: Sep 30th 2009

6

Thursday, February 24th 2011, 4:47pm

Quoted from "epix"

[...]
- 1 Aufgabe zeigen von regulär / kontextfrei
[...]

Interpretiere ich zuviel in diese Aussage hinein, wenn ich davon ausgehe, dass hoechstens die Erstellung von Grammatiken/Automaten/Kellerautomaten, aber *nicht* die Erstellung von (linear beschraenkten) Turingmaschinen dran kommt (abgesehen vom Thema Entscheidbarkeit/Berechnbarkeit)?

Go to the top of the page

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

7

Thursday, February 24th 2011, 5:01pm

Es gab auch eine Nachfrage zum LBA, und die Antwort ging eher so in die Richtung, dass dieser nicht drankommt.

Go to the top of the page

newgame

Trainee

Posts: 45

Date of registration: Sep 30th 2009

8

Thursday, February 24th 2011, 5:24pm

Quoted from "Bastian"

Es gab auch eine Nachfrage zum LBA, und die Antwort ging eher so in die Richtung, dass dieser nicht drankommt.

Alles klar, thx.

Go to the top of the page

cartman

Junior Schreiberling

Posts: 154

Date of registration: Mar 10th 2009

Location: Laatzen

9

Thursday, February 24th 2011, 6:38pm

nächste Frage, L:={a^n b^m | n mod m = 0}

da wirds bei mir schon schwierig bei der Wahl eines passenden Wortes x für das Pumping Lemma,
ein Wort aus dieser Sprache könnte ja aus 3 verschiedenen Arten bestehen,
1) a^0 b^n , n>=1
2) a^n b^m , n=m
3) a^n b^m , n=2m

zu1) mit x=b^n kommt man wohl nicht weiter, da dort beim Auf- oder Abpumpen das Wort in der Sprache wäre

zu2) da könnte man x=a^n b^n wählen, |x|>=n wäre erfüllt, aufgrund der ersten beiden Pumping-Lemma Bedingungen kann uv nur aus a's bestehen, und v zumindest aus einem a,
uv=a^k, k>=1
v=a^l, l>=1

=> uv²w = a^n-l a^2 b^n, dann wären es mehr a's als b's, aber es könnte jetzt wiederum vielleicht irgendwie so sein, dass damit Fall 3 eintritt und das Wort wieder in der Sprache ist

zu3) x=a^2n b^n
uv aus a's, v aus mindestens einem a, wenn man dann das v auf- oder abpumpt sollte das nicht mehr in L sein

normalerweise muss man ja erst das Wort wählen und dann die Fälle unterscheiden, aber wenn ich hier z.B. das Wort x=b^n wählen würde, kann ich die beiden anderen Fälle ja nicht mehr abhandeln

This post has been edited 1 times, last edit by "cartman" (Feb 24th 2011, 6:38pm)

Go to the top of the page

cartman

Junior Schreiberling

Posts: 154

Date of registration: Mar 10th 2009

Location: Laatzen

10

Thursday, February 24th 2011, 6:56pm

andere Aufgabe, L={a^n+m b^n c^m, n,m>=0}

Frage: ist L regulär ?

x = a^n+0 b^n c^0 = a^n b^n

|x|>=n, |uv|<=n, |v|>=1

v=a^l, l>=1

uv²w = a^n-l a² b^n
=> Wiederspruch, da es durch l>=1 und das aufgepumpte v jetzt mehr a's als b's wären

ist das weitgehend so in Ordnung (bis auf fehlenden Text, den man noch dazuschreiben sollte)

Go to the top of the page

Nagezahn

Junior Schreiberling

Posts: 198

Date of registration: Feb 9th 2010

Location: Nordstadt

11

Thursday, February 24th 2011, 10:26pm

Danke für die Infos! Hilft mir weiter.

Go to the top of the page

cartman

Junior Schreiberling

Posts: 154

Date of registration: Mar 10th 2009

Location: Laatzen

12

Friday, February 25th 2011, 2:27pm

Aufgabe: Geben sie einen endlichen Automaten M an, der die Sprache aller Wörter über {0,1} akzeptiert, deren erste zwei und letzte zwei Zeichen übereinstimmen, also L(M)=L mit

L = { w € {0,1}* | w=a1a2w'a1a2 für a1,a2€{0,1}, w'€{0,1}*}

Mit einem DEA oder NEA dürfte das doch nicht klappen, aber mit einem Kellerautomaten

- in Zustand 0 müssen 2 Zeichen gelesen und in den Keller geschrieben werden
- Zustand 1 deckt die Mitte ab, dort ist es egal, was gelesen wird, es darf auch nicht in den Keller geschrieben werden (darf man das hier so annehmen ?)
- in Zustand 2 werden dann die letzten beiden Eingaben mit den beiden im Keller verglichen

ist die Grundidee erstmal richtig ?

Go to the top of the page

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

13

Friday, February 25th 2011, 2:31pm

Weihe mich ein, wieso Du den Gedanken mit einem endlichen Automaten so schnell verwirfst?

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Go to the top of the page

cartman

Junior Schreiberling

Posts: 154

Date of registration: Mar 10th 2009

Location: Laatzen

14

Friday, February 25th 2011, 2:41pm

weil mir nicht in den Sinn kommen will, wie ich damit feststellen könnte, dass die ersten beiden zwei und die letzten beiden zwei Zeichen übereinstimmen,
Wörter aus dieser Sprache sind doch z.B. von der Form 01(w')01, 10(w')10, woher soll der Automat nach dem dritten Zeichen dann noch "wissen", was die ersten beiden waren

Go to the top of the page

Finn

Alter Hase

Posts: 126

Date of registration: Oct 10th 2010

15

Friday, February 25th 2011, 2:47pm

Weil du dir genau das merkst.

Es gibt 4 möglichkeiten:

00w00
01w01
10w10
11w11

du hast 4 zustände die das speichern und da gehst du einfach nicht deterministisch in eine schleife, und dann halt mit den entsprechen 2 zeichen wieder raus in den endzustand...

also wenn ich den baue komme ich auf 12 zustände edit: sehe gerade da kann man noch 2 weglassen und kommt auf 10

mfg Finn

Regierungen der industriellen Welt,...

This post has been edited 1 times, last edit by "Finn" (Feb 25th 2011, 2:53pm)

Go to the top of the page

Xular

Trainee

Posts: 62

Date of registration: Oct 7th 2007

16

Friday, February 25th 2011, 2:50pm

Durch die Zustandskodierung (Zs, Z0, Z1, Z00, Z01, Z10, Z11, ...) - mir fällt gerade allerdings nur ein recht "großer" DEA ein mit 1+2+4+8+1 Zuständen ... Geht bestimmt irgendwie eleganter.

edit: Jo, stimme dem OP zu, geht in 12 Zuständen... An Z00, Z01 etc kann man ja auch Schleifen dranbauen :>

edit2: Das hier dürfte eine mögliche Lösung sein, mit 12 Zuständen bin ich leider doch nicht so ganz hingekommen

Epic Paint Skillz:

This post has been edited 3 times, last edit by "Xular" (Feb 25th 2011, 3:16pm)

Go to the top of the page

Finn

Alter Hase

Posts: 126

Date of registration: Oct 10th 2010

17

Friday, February 25th 2011, 3:28pm

wow, ist der deterministische ja sogar einfacher als ich gedacht hätte

da ist aber noch ein kleiner fehler ;-)

die 0 aus Z01w0 muss in sich selbst gehen

das gleich mit der 1 aus Z10w1

grüße Finn

Regierungen der industriellen Welt,...

Go to the top of the page

Xular

Trainee

Posts: 62

Date of registration: Oct 7th 2007

18

Friday, February 25th 2011, 3:33pm

Ups stimmt natürlich, habs mal verbessert

Go to the top of the page

cartman

Junior Schreiberling

Posts: 154

Date of registration: Mar 10th 2009

Location: Laatzen

19

Friday, February 25th 2011, 6:32pm

danke für die Hilfe, und ich wollt so sicher in den Keller gehen :-)

Jetzt hab ich mich noch an den weiteren versucht (mit Ausnahme des Automaten, der die Binärzahlen, die durch 3 teilbar sind akzeptiert)

[1]