Loesungen FGdI1 Klausuren

Michael Ries
Neuling
Neuling
Beiträge: 4
Registriert: 6. Apr 2011 16:34

Loesungen FGdI1 Klausuren

Beitrag von Michael Ries » 25. Aug 2011 12:52

Hat irgendwer Loesungen zu den Klausuren ...

Oder schon welche selber durchgerechnet ???

Bin nämlich auch gerade dabei und würde gerne mal vergleichen.

-py-
Windoof-User
Windoof-User
Beiträge: 27
Registriert: 18. Mär 2011 00:27

Re: Loesungen FGdI1 Klausuren

Beitrag von -py- » 29. Aug 2011 22:54

Ich hab die Klausur vom WS09/10 bearbeitet und würde gern die Ergebnisse vergleichen. Ich bin allerdings nicht unbedingt der fitteste in FGdI und daher werden sicherlich Fehler in meinen Ergebnissen sein. Es wäre also nett, wenn jemand sagen könnte, was ich wo falsch gemacht hab ^^

Aufgabe 1:
a) wahr
b) wahr
c) wahr (?)
c) und d) konnte ich nicht beantworten. Kennt da jemand die richtige Antwort?


Aufgabe 2:
a) ((a+b+c)(a+b+c)(a+b+c))*
Bild

b) (a+b+c)*a(a+ba+c)*
Bild

c) Hab ich nicht hingekriegt


Aufgabe 3:
a)
Bild

b)
Bild


Aufgabe 4:
a)
Bild

b) a*bb*(aa+aba*b)*


Aufgabe 5:
a)
(i)
\(S \rightarrow X\)
\(X \rightarrow a | b | (X) | XX | \varepsilon\)
(ii)
\(S \rightarrow XaX\)
\(X \rightarrow b | XX | aXa | (X) | \varepsilon\)

b)
\(S \rightarrow CZ_{(S)} | SZ_{cS} | a\)
\(Z_{(S)} \rightarrow Z_{(}Z_{S)}\)
\(Z_{S)} \rightarrow SZ_{)}\)
\(Z_{cS} \rightarrow Z_{c}S\)
\(X \rightarrow Z_{(}Z_{X)} | b | XZ_{dX}\)
\(Z_{X)} \rightarrow XZ_{)}\)
\(Z_{dX} \rightarrow Z_{d}X\)
\(Z_{(} \rightarrow (\)
\(Z_{)} \rightarrow )\)
\(Z_{c} \rightarrow c\)
\(Z_{d} \rightarrow d\)


Aufgabe 6:
a)
\(S \rightarrow aSa | aSb | \varepsilon\)

Angenommen \(L_1\) ist regulär. Nach dem Pumping Lemma gibt es ein \(n \in \mathbb N\), sodass sich jedes \(x \in L_1\) mit \(|x| \geq n\) zerlegen lässt als \(x = rst\) mit \(|s|>0\), \(|rs| \leq n\) und \(rs^kt \in L_1\) für alle \(k \in \mathbb N\).
Sei \(n \in \mathbb N\) beliebig. Wir betrachten \(x = a^nw\) mit \(|w|=n\).
Wegen \(|rs| \leq n\) gilt \(r = a^i\), \(s=a^j\),\(t=a^{n-i-j}w\) mit \(|w|=n\) für ein \(j \neq 0\) und \(i+j \leq n\).
Für \(k = 2\) gilt \(rs^2t = a^ia^{2j}a^{n-i-j}w = a^{n+j}w\) \(\notin L_1\), was ein Widerspruch des Pumping Lemmas ist. Somit ist \(L_1\) nicht regulär.

(b) Hab ich noch nicht bearbeitet.
Zuletzt geändert von -py- am 30. Aug 2011 15:04, insgesamt 1-mal geändert.

Flora
Erstie
Erstie
Beiträge: 16
Registriert: 22. Mär 2011 16:20

Re: Loesungen FGdI1 Klausuren

Beitrag von Flora » 30. Aug 2011 14:34

Hier mal meine Lösungen:

Aufgabe 1 (abgeklärt mit dem Tutor)
a) wahr
b) wahr
c) falsch
d) wahr
e) falsch


Aufgabe 2
a) richtig
b) meines Erachtens nach falsch. Richtig wäre (a+b+c)*a
Bild
c) (b+c)* ( a(b+c)* + a(b+c)^+ (a (b+c)^+ )*
Bild


Aufgabe 3
- stimme ich mit überein, nach einer Information die ich heute vom Tutor erhielt. Demnach MÜSSEN beim DFA aus jedem Zustand immer alle Buchstaben der Sprache ausgehend sein (siehe Zustand 3 -> b muss zu Knoten mit { } )


Aufgabe 4
- stimme ich mit überein


Aufgabe 5
a) gibt es bei einer kontextfreien Grammatik epsilon-Produktionen? Meine Grammatiken sehen wie folgt aus:
(i)
S -> K | L
K -> ( ) | ( K ) | L
L -> a | b | aL | bL | K

(ii)
S -> K | L
K -> ( ) | ( K ) | L
L -> aaL | aaA | bL | bA | bB
A -> a | ab
B -> b


Aufgabe 6
- selbe Frage: gibt es epsilon-Produktionen bei kontextfreien Sprachen? Meine Sprache lautet:
S -> X
X -> aXR
R -> a | b

-py-
Windoof-User
Windoof-User
Beiträge: 27
Registriert: 18. Mär 2011 00:27

Re: Loesungen FGdI1 Klausuren

Beitrag von -py- » 30. Aug 2011 14:58

Flora hat geschrieben:Hier mal meine Lösungen:

Aufgabe 1 (abgeklärt mit dem Tutor)
a) wahr
b) wahr
c) falsch
d) wahr
e) falsch
Danke :)

Flora hat geschrieben:Aufgabe 2
b) meines Erachtens nach falsch. Richtig wäre (a+b+c)*a
Bild
Dieser reguläre Audrück würde nach dem letzten a aber auch keine c mehr erlauben.

Flora hat geschrieben:c) (b+c)* ( a(b+c)* + a(b+c)^+ (a (b+c)^+ )*
Bild
Was macht denn (b+c)^+? Ich dachte, wir dürfen nur \(\cdot\), + und * in regulären Ausdrücken benutzen.
Der Automat sieht mir nicht ganz korrekt aus, da er das Wort aca akzeptieren würde, was aber nicht in der Sprache ist.

Flora hat geschrieben:Aufgabe 5
a) gibt es bei einer kontextfreien Grammatik epsilon-Produktionen?
Laut Wikipedia schon:
Wikipedia hat geschrieben:Kontextfreie Sprachen können das leere Wort enthalten, z. B. durch eine Produktionsregel \((S \rightarrow \varepsilon)\).

Flora
Erstie
Erstie
Beiträge: 16
Registriert: 22. Mär 2011 16:20

Re: Loesungen FGdI1 Klausuren

Beitrag von Flora » 30. Aug 2011 15:11

-py- hat geschrieben:
Flora hat geschrieben:Aufgabe 2
b) meines Erachtens nach falsch. Richtig wäre (a+b+c)*a
Bild
Dieser reguläre Audrück würde nach dem letzten a aber auch keine c mehr erlauben.

Du hast Recht. Also noch eine Schleife mit c's hinten auf Zustand 2.
-py- hat geschrieben:
Flora hat geschrieben:c) (b+c)* ( a(b+c)* + a(b+c)^+ (a (b+c)^+ )*
Bild
Was macht denn (b+c)^+? Ich dachte, wir dürfen nur \(\cdot\), + und * in regulären Ausdrücken benutzen.
Der Automat sieht mir nicht ganz korrekt aus, da er das Wort aca akzeptieren würde, was aber nicht in der Sprache ist.

Damit ist "hoch +" gemeint. Ähnlich dem Stern, nur dass dieser aussagt, dass es mindestens 1 Transition geben muss.
Richtiger wäre dann wohl:
Bild

-py- hat geschrieben:
Flora hat geschrieben:Aufgabe 5
a) gibt es bei einer kontextfreien Grammatik epsilon-Produktionen?
Laut Wikipedia schon:
Wikipedia hat geschrieben:Kontextfreie Sprachen können das leere Wort enthalten, z. B. durch eine Produktionsregel \((S \rightarrow \varepsilon)\).
Dann ist deinen Regeln nichts hinzuzufügen.

-py-
Windoof-User
Windoof-User
Beiträge: 27
Registriert: 18. Mär 2011 00:27

Re: Loesungen FGdI1 Klausuren

Beitrag von -py- » 30. Aug 2011 15:28

Flora hat geschrieben:Damit ist "hoch +" gemeint. Ähnlich dem Stern, nur dass dieser aussagt, dass es mindestens 1 Transition geben muss.
Also wäre \((b+c)^+\) im Prinzip das gleiche wie (b+c)(b+c)*?
Flora hat geschrieben:Richtiger wäre dann wohl:
Bild
Bin immer noch nicht einverstanden ^^ abaca akzeptiert der Automat auch.
Ich glaub, das c auf dem Pfeil vom Zustand 3 nach 2 müsste noch weg und auf dem c-Pfeil von Zustand 2 müsste noch ein b dazu. Dann könnte es stimmen.

L.A.
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 14. Dez 2009 14:48

Re: Loesungen FGdI1 Klausuren

Beitrag von L.A. » 30. Aug 2011 21:29

Bild

ich hab des so bei der 2 c)

was meint ihr?


Zu 5 a) i)
soweit ich das verstehe dürfen kontextfreie Grammatiken nur harmlose e-Produktionen haben.
meine Lösung daher:
X -> e
X -> a | b | (X) | () | XX

Kristoffer
Windoof-User
Windoof-User
Beiträge: 35
Registriert: 4. Okt 2010 21:29

Re: Loesungen FGdI1 Klausuren

Beitrag von Kristoffer » 31. Aug 2011 08:43

L.A. hat geschrieben: Zu 5 a) i)
soweit ich das verstehe dürfen kontextfreie Grammatiken nur harmlose e-Produktionen haben.
meine Lösung daher:
X -> e
X -> a | b | (X) | () | XX
Habe in etwa die gleiche Lösung, du meinst aber doch sicher:
S -> X | e
X -> a | b | (X) | () | XX
Flora hat geschrieben:
Aufgabe 5
(ii)
S -> K | L
K -> ( ) | ( K ) | L
L -> aaL | aaA | bL | bA | bB
A -> a | ab
B -> b
Bei deiner Lösung kann man kein (a) bilden.

L.A.
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 14. Dez 2009 14:48

Re: Loesungen FGdI1 Klausuren

Beitrag von L.A. » 31. Aug 2011 10:23

Achja richtig. Es muss S -> X | e sein sonst ist es keine harmlose e-produktion, oder?

danny
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 17. Okt 2010 22:32

Re: Loesungen FGdI1 Klausuren

Beitrag von danny » 31. Aug 2011 12:35

Genau

L.A.
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 14. Dez 2009 14:48

Re: Loesungen FGdI1 Klausuren

Beitrag von L.A. » 31. Aug 2011 13:27

Hat zufällig mal jemand die ws 04/05 , ws 05/06 oder SS 05 Klausuren gerechnet? Oder will jemand sowas haben?

danny
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 17. Okt 2010 22:32

Re: Loesungen FGdI1 Klausuren

Beitrag von danny » 31. Aug 2011 13:31

Wenn es sich um FGdI 1 Klausuren handelt, wäre es toll, wenn du sie hochladen könntest.

L.A.
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 14. Dez 2009 14:48

Re: Loesungen FGdI1 Klausuren

Beitrag von L.A. » 31. Aug 2011 14:23

http://uploaded.to/file/ee7w0ieq

Hier mal die 3 hochgeladen.
Wäre toll wenn ihr eure Ergebnisse auch hier reinstellen könntet. Ich werde das auch tun falls ich heute noch Zeit habe ....
Arbeit und so :(

Ankou
Mausschubser
Mausschubser
Beiträge: 85
Registriert: 15. Mai 2011 18:23

Re: Loesungen FGdI1 Klausuren

Beitrag von Ankou » 31. Aug 2011 15:11

soweit ich das verstehe dürfen kontextfreie Grammatiken nur harmlose e-Produktionen haben.
nein, kontextsensitive Grammatiken dürfen nur harmlose \(\varepsilon\)-Produktionen haben, kontextfreie Grammatiken dürfen jedwede \(\varepsilon\)-Produktion haben.
Deswegen ist auch nicht jede kontextfreie Grammatik gleichzeitig eine kontextsensitive Grammatik, aber jede kontextfreie Grammatik ist äquivalent zu einer kontextsensitiven Grammatik/einer kontextfreien Grammatik nur mit harmloser \(\varepsilon\)-Produktion, sodass jede kontextfreie Sprache gleichzeitig auch kontextsensitiv ist, siehe dazu Beobachtung 3.2.5 im Script und das vorhergehende Lemma.
4. b) a*bb*(aa+aba*b)*
babbb wird vom Automaten erkannt, aber passt nicht auf deinen Ausdruck.

-py-
Windoof-User
Windoof-User
Beiträge: 27
Registriert: 18. Mär 2011 00:27

Re: Loesungen FGdI1 Klausuren

Beitrag von -py- » 31. Aug 2011 15:48

Ankou hat geschrieben:
4. b) a*bb*(aa+aba*b)*
babbb wird vom Automaten erkannt, aber passt nicht auf deinen Ausdruck.
Stimmt, ich hab einen Pfeil nicht beachtet. a*bb*(aa+aba*bb*)* müsste dann aber stimmen, hoffe ich ^^


Ich habe auch nochmal lange über Aufgabe 2c nachgedacht und bin zu dem Ergebnis gekommen:

(b+c)*(a(b+c)*b(b+c)*)*a(b+c)*+(b+c)*

Bild

Meinungen?

Antworten

Zurück zu „Archiv“