GThI Klausur-Aufgaben WS 09/10 und Klausur SS 2010

Trainee

Date of registration: Sep 12th 2008

Monday, August 30th 2010, 9:12pm

So, jetzt habe ich auch mal ein paar GThI-Fragen, und zwar zur Klausur vom letzten Semester (16.02.2010) (kommt mir das nur so vor, oder ist die tatsächlich deutlich abgedrehter als die Klausuren der Jahre zuvor?)

Aufgabe 2

Geben Sie einen deterministischen endlichen Automaten M an, für den gilt:

$L(M) = \{w \in \{0,1\}^* | w$ ist die Binärdarstellung (evtl. mit führenden Nullen) einer Zahl $n \in \mathbb{N}$ , die durch 3 teilbar ist $\}$

Ich scheitere bereits daran, daß ich keinen Plan davon habe, wie eine durch 3 teilbare Zahl in Binärdarstellung überhaupt aussieht. In Dezimaldarstellung ist es klar: die Quersumme ist durch 3 teilbar. Aber binär? Ich habe mir mal die entsprechenden Zahlen bis 24 aufgeschrieben, kann da aber auch keinerlei System entdecken.

Mit Google finde ich folgende Produktion: N -> 11 | 1001 | N0 | NN
Abgesehen davon, daß ich mich auch hier wieder frage "Wie kommt man darauf?" ist das ja zudem noch eine Typ2-Grammatik, hilft auf der Suche nach einem DEA also auch nicht weiter.

Aufgabe 4

Sei $G := \(\{S, A, B\}, \{a, b\}, P, S\}$ mit
$P:=\{ S \rightarrow AB, A \rightarrow aAa | a, B \rightarrow bBb | b\}$ .

a) Von welchem Typ ist die Grammatik G?
b) Von welchem Typ ist die Sprache L(G)?
Begründen Sie Ihre Antworten!

Irgendwie verstehe ich hier die Frage nicht. Klar, die Grammatik ist vom Typ 2: rechte Seiten der Produktionen sind mindestens genauso lang, wie die linken Seiten der Produktionen, linke Seite der Produktionen sind einzelne Variablen (würde das als Begründung schon ausreichen?)
Aber was wird jetzt bei Teil b erwartet? Selbst im Skript wird mal von Typ-i-Grammatik und mal von Typ-i-Sprache geredet, bzw. z.B. von kontextfreier Sprache und kontextfreier Grammatik. Wo ist hier also der Unterschied?

Aufgabe 5
Geben Sie eine kontextfreie Grammatik G an, für die gilt:

$L(G) = \{w \in \{0,1\}^* | \text{ fuer alle } u, v \in \{0,1\}^* \text{ mit } w = uv \text{ gilt: } |u|_0 \geq |u|_1\}$

L(G) ist also die Sprache aller Wörter w, für die gilt, dass jedes Präfix von w mindestens so viele 0en wie 1en enthält.

Gibt es hier irgendwie eine systematische Heransgehensweise? Ich habe hier zwar durch (zu langes) Herumprobieren eine Grammatik gefunden, wobei ich mir aber nicht wirklich sicher bin, ob sie wirklich korrekt ist ...

So weit bin ich:

sowohl w, als auch u und v scheinen ja aus dem leeren Wort bestehen zu können, daher als Start folgendes (A sorgt dann für die Produktionen des Präfixes, E für das Suffix):
S -> $\varepsilon$ | AE | A | E

Das Suffix ist dann beliebig:
E -> 0 | 1 | 0E | 1E

Beim Präfix wird's dann sehr vie komplizierter

die 0 kann beliebig oft und an beliebiger Stelle erzeugt werden:
A -> 0 | 0A | A0

wenn eine 1 kommt, dann brauchen wir eine Variable, die uns sagt, wir brauchen auch eine 0 dazu:
A -> 1B|B1
B -> 0 | 0A | A0
und danach geht das Spiel wieder von vorne los ...

Keine Ahnung, ob die wirklich so korrekt ist ...

Fragen über Fragen, ich hoffe, es kann irgendjemand Licht ins Dunkle bringen ...

Viele Grüße
Carsten

This post has been edited 1 times, last edit by "Panoramix" (Aug 30th 2010, 9:16pm)

Go to the top of the page

Panoramix

Trainee

Posts: 115

Date of registration: Sep 12th 2008

2

Monday, August 30th 2010, 9:37pm

Quoted from "Panoramix"

Aufgabe 4

Sei $G := \(\{S, A, B\}, \{a, b\}, P, S\}$ mit
$P:=\{ S \rightarrow AB, A \rightarrow aAa | a, B \rightarrow bBb | b\}$ .

a) Von welchem Typ ist die Grammatik G?
b) Von welchem Typ ist die Sprache L(G)?
Begründen Sie Ihre Antworten!

Ich glaube, die Frage habe ich jetzt verstanden:

Die Grammatik ist zwar vom Typ 2, die Sprache selbst (ungerade Anzahl a's gefolgt von ungerader Anzahl b's) ist aber regulär.

Viele Grüße
Carsten

Go to the top of the page

FSW16

Trainee

Posts: 119

Date of registration: Jun 25th 2008

Location: Hildesheim

3

Monday, August 30th 2010, 9:48pm

Bei Aufgabe 2 bin ich folgendermaßen vorgegangen:

ich habe 3 Zustände:
z1: "bisherige Binärzahl" mod 3 = 1
z2: "bisherige Binärzahl" mod 3 = 2
z3: "bisherige Binärzahl" mod 3 = 0 ist auch gleich Endzustand
und
dann natürlich den Startzustand z0

und jetzt musst du nur noch gucken wie sich der "Rest" ändert wenn du eine 1 oder eine 0 an das Ende der bisherigen Binärzahl anfügst.

Das führt dann zu:
(z0,0)-> z3
(z0,1)-> z1
(z1,0)-> z2
(z1,1)-> z3
(z2,0)-> z1
(z2,1)-> z2
(z3,0)-> z3
(z3,1)-> z1

so müssten dann die Übergangsfunktionen aussehen.

Ich hoffe, dass ist einigermaßen verständlich.

Edit: Bei Aufgabe 4 hast du das so richtig erkannt und zwar musst du einfach nur gucken, ob du die Sprache L nicht auch mit einer anderen Grammatik erzeugen kannst die Typ 3 ist und das ist in diesem Fall so, wie du es ja schon gesagt hast.

Edit2: Tipp zu Aufgabe 5: bisher hast du eine reguläre Sprache erzeugt, aber es soll ja "nur" eine kontextfreie Sprache werden, also dürfen die Ableitungen aus mehr als nur einem Terminal und einer Variable bestehen.

This post has been edited 2 times, last edit by "FSW16" (Aug 30th 2010, 10:00pm)

Go to the top of the page

Helicase

Trainee

Posts: 85

Date of registration: Oct 3rd 2006

4

Monday, August 30th 2010, 9:50pm

Zu Aufgabe 4. Wie Panoramix schon gesagt hat: Man kann ja eine reguläre Sprache auch durch eine Grammatik beschreiben, die nicht regulär ist. Oder anders, auch wenn es eine Grammatik vom Typ 2 gibt, kann es ja trotzdem ne "bessere" Grammatik in Typ 3 geben.

Zu Aufgabe 2:
Es gilt die alternierende Quersummenregel, da 3 = 2+1 (wie im 10er system bei 11=10+1). Also z.B. ist die Zahl 121 durch 11 teilbar.. naja ist 1-2+1 durch 11 teilbar.. ja da 0 durch 11 teilbar. Bei binärzahlen ist das ähnlich einfach.. mit 6 Zuständen kriegt man da leicht was hin.. einfach
if(eingabe == 1 && gerade stelle) summe+1
if(eingabe == 1 && ungerade stelle) summe -1

und dann musst du halt nur noch in der Restklasse das machen, also 3 für gerade stellen.. 3 für ungerade stellen.

Aufgabe 5: hab ich nur überflogen ist vielleicht etwas technischer, aber sicherlich nicht unbedingt schwer. Musst halt an jeder stelle sicher stellen, dass es bis dahin mehr nullen als einsen gibt.

edit:
FSW16 methode zu aufgabe 2 sieht auch ganz gut aus

(ausprobieren bringt manchmal mehr als reine mathematik

)

This post has been edited 1 times, last edit by "Helicase" (Aug 30th 2010, 9:52pm)

Go to the top of the page

Spunkmeyer

Trainee

Posts: 64

Date of registration: Apr 2nd 2008

Location: Wunstorf

Occupation: Programmierer

5

Monday, August 30th 2010, 9:58pm

Zu 4:
ist die Sprache nicht $L(G) = \{a^nb^n | n \in \mathbb{N}, n \ge 1\}$ ? Und damit Typ 2? (edit: hab da übersehen, das die a's und b's unabhängig sind, daher ist meine Vermutung falsch!)

Zu 5:
Es geht um ALLE präfixe, daher meine Produktion:
S -> 0 | 0A | 0B1 | 0B1A
A -> 0 | 1 | 0A | 10A | 10 | 0B1 | 0B1A
B -> 0B1 | 01

Und was schreibt man bei Aufgabe 6?

DEADBEEF = 3735928559

Mein Weblog: www.dev.spunkmeyer.de

This post has been edited 1 times, last edit by "Spunkmeyer" (Aug 30th 2010, 10:20pm)

Go to the top of the page

FSW16

Trainee

Posts: 119

Date of registration: Jun 25th 2008

Location: Hildesheim

6

Monday, August 30th 2010, 10:01pm

@ Spunkmeyer: Zu4 Meiner Meinung nach kannst du auch aaab oder abbb ohne Probleme ableiten.
Zu5: da sieht die Lösung von Spunkmeyer meiner Meinung nach sehr gut aus, außer dass das leere Wort fehlt.

This post has been edited 3 times, last edit by "FSW16" (Aug 31st 2010, 11:56am)

Go to the top of the page

Spunkmeyer

Trainee

Posts: 64

Date of registration: Apr 2nd 2008

Location: Wunstorf

Occupation: Programmierer

7

Monday, August 30th 2010, 10:04pm

@FSW16: Stimmt, du hast recht, die sind ja unabhängig... Ganz übersehen. Hoffentlich passiert mir das in der Klausur nicht :-)

DEADBEEF = 3735928559

Mein Weblog: www.dev.spunkmeyer.de

Go to the top of the page

Panoramix

Trainee

Posts: 115

Date of registration: Sep 12th 2008

8

Monday, August 30th 2010, 10:09pm

Danke für Eure Antworten! "alternierende Quersummenregel"???ßßesszett Nie gehört!!!11einself Sowas soll man in der Klausur wissen? :wacko:

Auf die Aufgabe hätte ich im Ernstfall definitiv 0 Punkte bekommen ...

Quoted from "Spunkmeyer"

Zu 4:
ist die Sprache nicht $L(G) = \{a^nb^n | n \in \mathbb{N}, n \ge 1\}$ ? Und damit Typ 2?

Nee, die Anzahl der a's und b's ist ja unabhängig voneinander. Die Sprache müßte so lauten:
$L(G) = \{a^{2n+1}b^{2m+1} | n,m \in \mathbb{N}, n,m \geq 0\}$

Quoted from "Spunkmeyer"

Zu 5:
Es geht um ALLE präfixe, daher meine Produktion:
S -> 0 | 0A | 0B1 | 0B1A
A -> 0 | 1 | 0A | 10A | 10 | 0B1 | 0B1A
B -> 0B1 | 01

Das Wort könnte z. B. auch mit einer 1 anfangen. Das ist bei dir gar nicht möglich ...

Viele Grüße
Carsten

Edit: Latex-Murx korrigiert und FSW16 war etwas schneller ...

This post has been edited 2 times, last edit by "Panoramix" (Aug 30th 2010, 10:25pm)

Go to the top of the page

Spunkmeyer

Trainee

Posts: 64

Date of registration: Apr 2nd 2008

Location: Wunstorf

Occupation: Programmierer

9

Monday, August 30th 2010, 10:12pm

Hi Carsten,

wenn das Wort mit 1 anfängt, gibt es ein Präfix, welches die Regel mehr oder gleichviele 0 zu enthalten verletzt. Oder hab ich das falsch verstanden?

Viele grüße,
Thomas

DEADBEEF = 3735928559

Mein Weblog: www.dev.spunkmeyer.de

Go to the top of the page

FSW16

Trainee

Posts: 119

Date of registration: Jun 25th 2008

Location: Hildesheim

10

Monday, August 30th 2010, 10:14pm

Ne mit 1 darf es nicht anfangen, denn dann wäre ein Präfix ja aufjedenfall 1 und die Vorschrift, dass mehr oder gleich viele 0en als 1en in jedem Präfix vorkommen, würdest du damit also nicht einhalten.

Edit: Mist zu langsam

This post has been edited 2 times, last edit by "FSW16" (Aug 30th 2010, 10:15pm)

Go to the top of the page

Panoramix

Trainee

Posts: 115

Date of registration: Sep 12th 2008

11

Monday, August 30th 2010, 10:19pm

So langsam dämmert mir, daß ich Aufgabe 5 vollkommen falsch verstanden habe ...
Noch ein 0-Punkte-Kanditat ...

Danke für die Erleuchtung!

This post has been edited 1 times, last edit by "Panoramix" (Aug 30th 2010, 10:20pm)

Go to the top of the page

FSW16

Trainee

Posts: 119

Date of registration: Jun 25th 2008

Location: Hildesheim

12

Monday, August 30th 2010, 10:26pm

Weiß eigentlich jemand, ob die Klausur dieses Jahr auch so aussehen wird wie letztes Semester? Also, dass man sich aus 5 Aufgaben 3 auswählen kann und dann dazu noch eine Multiple-Choice Aufgabe?

MfG FSW

This post has been edited 1 times, last edit by "FSW16" (Aug 30th 2010, 10:29pm)

Go to the top of the page

Panoramix

Trainee

Posts: 115

Date of registration: Sep 12th 2008

13

Monday, August 30th 2010, 10:30pm

Quoted from "FSW16"

Weiss eigentlich jemand, ob die Klausur dieses Jahr auch so aussehen wird wie letztes Semester? Also, dass man sich aus 5 Aufgaben 3 auswählen kann und dann dazu noch eine Multiple-Choice Aufgabe?

Bei der Anzahl der Aufgaben bin ich gerade überfragt. Aber sonst so wie Du gesagt hast: eine Multiple-Choice Aufgabe und vom Rest eine bestimmte Anzahl auswählen (das war in den älteren Klausuren auch schöner ...)

Viele Grüße
Carsten

Go to the top of the page

Spunkmeyer

Trainee

Posts: 64

Date of registration: Apr 2nd 2008

Location: Wunstorf

Occupation: Programmierer

14

Tuesday, August 31st 2010, 8:55am

Wenn ich es richtig verstanden habe, bekommen wir 1 MultipleChoice als Pflicht und von den weiteren 4 Aufgaben können wir uns 3 aussuchen.

DEADBEEF = 3735928559

Mein Weblog: www.dev.spunkmeyer.de

Go to the top of the page

Peter

Praktikant

Posts: 31

Date of registration: Feb 1st 2008

15

Tuesday, August 31st 2010, 10:34am

@Spunkmeyer: Bei deiner Lösung von A5 könnte man S => 0B1A => 0011A => 001110 ableiten und das darf nicht sein, weil dann für u=00111, v=0 die bedingung verletzt wäre.
Eine richtige Lösung wäre z.B.
S -> epsilon | T
T -> TT | 0T | 0T1 | 0 | 01
Ein genereller "Tipp", wie man auf sowas kommt: Sich die rekursive Struktur eines Wortes aus der Sprache überlegen: Wenn ich ein Wort habe, wie kann ich daraus neue bauen.
Außerdem: Versuchen, die Grammatik möglichst einfach zu halten und ohne viele Sonderfälle auszukommen.

Zur Binärzahl durch 3 teilbar-Aufgabe:
Man soll natürlich nicht die Regel mit der alternierenden Quersumme wissen. (Die kannte ich bis eben auch noch nicht.) Sondern man soll es so machen wie FSW16s Lösung.

Zum Klausurmodus:
Es gibt eine Multiple-Choice-Aufgabe, die auf jeden Fall gewertet wird und dann noch vier Aufgaben, von denen (die besten) drei gewertet werden. Ihr dürft euch also eine Aufgabe aussuchen, die ihr nicht bearbeiten müsst.

Go to the top of the page

Skuld

Erfahrener Schreiberling

Posts: 344

Date of registration: Oct 2nd 2007

Occupation: Student

16

Tuesday, August 31st 2010, 1:00pm

Zur Klausur - Hilfsmittel sind doch ein beidseitig beschriebenes A4 Blatt?

Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?

Go to the top of the page

Peter

Praktikant

Posts: 31

Date of registration: Feb 1st 2008

17

Tuesday, August 31st 2010, 1:02pm

Ja, genau. Es darf auch bedruckt statt beschrieben sein.

Go to the top of the page

Xular

Trainee

Posts: 62

Date of registration: Oct 7th 2007

18

Tuesday, August 31st 2010, 2:49pm

Hm, wenn ich mir da Aufgabe 1 dieser Klausur anschaue komme ich auf

1,2 richtig
3,4,5 falsch
6,7,8 richtig

Das wäre ja ne merkwürdige Antwortenverteilung, also wo lieg ich falsch?

Zu einigen Sachen find ich nichts im Wiki / den Übungen...

edit: Und was die Aufgabe 3 angeht, würde es da schon reichen, zu zeigen, dass die Bedingung |x| = |y| nicht erfüllt werden kann? Das läuft ja auf x^n y^n hinaus, wenn x,y aus einem Zeichen bestehen -> Standardwiderlegung mit PL

This post has been edited 1 times, last edit by "Xular" (Aug 31st 2010, 3:11pm)