Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
ti-wiederholungsklausur 2004
hi,
mir ist ein scan der ti-wiederholungsklausur vom fruehjahr 2004 in die haende gekommen und denke mir, dass ihr auch ganz geil auf diesen seid…
gruesse,
-steppenwolf
Attachment:
TI-Klausur2004.pdf: https://fsi.cs.fau.de/unb-attachments/post_15194/TI-Klausur2004.pdf
Cool, danke! Weisst du wer den TI2 Teil gestellt hat? Der ist schon noch von Prof. Leeb, oder?
Und kann mir vielleicht mal jemand erklären, wie wir diese RSA Aufgaben lösen sollen, bei denen nur n und e bekannt ist? Sofern ich das richtig verstanden habe läuft das auf rumprobieren raus, aber das kann doch nicht das wahre sein, oder?
hi,
TI2 Teil stammt von Prof. Stoyan nicht von Leeb
kann mir jemand mal erklären welche der sprachen aus I-2 regulär sind ??
ich hab mir das nämlich so gedacht:
L(1,n) erzeugt auch Wörter der Form a^nb^n, damit ist das eine echte Teilmenge von L(1,n) damit kann dann auch L(1,n) nicht regulär sein
oder auch
der in I-1b zu konstruierende Automat entspricht L(1,2) → Wörter der länge 2n ( n = 2 ) → 4
man sieht an dem Automaten schon dass man allgemein für n aus N keinen Automaten zeichnen kann, denn der hätte dann für n->unendlich unendlich viele zustände
→ L(1,n) nicht regulär
L(3,n): auch hier a^nb^n erzeugbar → gleiche Argumentation wie L(1,n)
Automat I-1a entspricht L(3,2)
→ L(3,n) nicht regulär
und L(2,n) kann Wörter der Form a^nb^nb^n erzeugen die auch nicht regulär sind
???
zu welchen sprachen soll also in I-2d ein Automat angegeben werden
danke für hilfe
L(1,n) macht doch eigentlich Worte der Form w € (a,b)* | l(w) = gerade.
Dafür gibt es eine einfache reguläre Grammatik:
S-> aT, bT
T → aU, bU
U → aT, bT, e
die anderen sind glaube ich nicht regulär. Ausserdem kann man das doch bestimmt noch anders zeigen, als mit einer Grammatik, oder?
Und die Schreibweise von M verstehe ich nicht. Was soll das “oder-Zeichen” am Anfang bedeuten?
die sind alle regulär!
L_1,n besteht nur aus Wörtern der Länge 2n (= anzahl der a’s+ anzahl der b’s). es ist von einem Automaten der größe 2n+1 akzeptierbar!
Der hat ungefähr folgende Form:
(1=S) ->a,b (2) ->a,b … ->a,b ((2n)) ->a,b (2n+1) ->(2n+1)
Also: (Prosaversion): Startzustand (1) geht mit a oder b in (2) über geht mit a oder b in (3) über geht (…) in ((2n)) über dies ist der Endzustand. kommen weitere a oder b’s geht der automat von ((2n)) nach (2n+1) und bleibt dort.
wie man leicht sieht ist dies ein DFA → L_1,n regulär.
L_2,n: 3n+1 zustände (1) startzustand, ((3n)) endzustand:
1 <= z < 3n: (z) ->a (z+1) ; (z) ->b (z+2) automat geht vom zustand (z) mit a über in (z+1) ober mit b in (z+2) solange z<3n.
3n <= z <= 3n+1: (z) ->a,b (3n+1) automat geht vom zustand (z) mit egal was nach (3n+1) und bleibt dort.
Auch dies ist ein DFA
L_3,n ; M_i: reguläre Sprachen sind bezüglich Vereinigung und Schnitt abgeschlossen. daher sind die Sprachen nach aufgabe a) ebenfalls regulär.
@Robert:
deine Grammatik ist richtig für M_1.
(vereinigung aller sprachen mit FESTER gerader Wortlänge = Sprache mit gerader Wortlänge)
Gut. Meine Loesungen (bzw die Loesungen unsrer Lerngruppe):
L(1,n) nicht regulaer. Und zwar genau deswegen:
L(3,n) nicht regulaer. 100pro. Wir haben naemlich schon in einer TI1-Uebung gezeigt, dass Laenge von a = Laenge von b nicht regulaer ist.
L(2,n) ist regulaer. Denn dazu kann man einen deterministischen Automaten zeichnen.
was habt ihr bei I-2 b) ?
Hmm und wenn ich für L1,n sowas produziere:
[ab]{2n} als regulären Ausdruck?
Der gibt 2n Zeichen aus, die entweder ein a oder ein b sein können - die Summe der a und b ergibt also 2n - was ist daran jetzt nicht regulär?
Sprachen mit wörtern fester Länge sind immer regulär.
man kann die wörter dann ja aufzählen also auch einen trivialen automaten angeben, der einfach alle gültigen worte als endzustände hat (und das sind hier (L(1,n) im Maximalfall 2^(2n) !!! → DFA)
(habe oben einen besseren angegeben)
für M_1 = {w | #(a,w) + #(b,w) = 0 mod 2}
M_2 = {w | #(a,w) + 2*#(b,w) = 0 mod 3}
diese beiden sind sowas von regulär!
M_3 = {w | #(a,w) = #(b,w)} ist nicht regulär (sorry, hab ich oben falsch hingeschrieben)
zu :
Quote by alexv:
L(1,n) erzeugt auch Wörter der Form a^nb^n, damit ist das eine echte Teilmenge von L(1,n) damit kann dann auch L(1,n) nicht regulär sein
Das pumping lemma sagt:
es Existiert eine Zahl p \in N so dass füralle uvw \in L mit |uvw| >= p
uv^(i)w \in L und |uv| < p
bei L(1,n) kann man dieses p ganz einfach als 2n+1 wählen. Wie man sieht kann man ALLE (0 an der Zahl, da die Länge eines jeden Wortes in L(1,n) nunmal 2n ist. (es sei denn, ihr habt mehr buchstaben als ich(bin im Besitz von {a,b}))) pumpen wo man will und sie bleiben in L(1,n). das Pumping Lemma ist also erfüllt, da ich so ein p angeben kann.
Nachdem auch L2,n regulär ist, so muss auch L3,n regulär sein, weil reguläre Sprachen über Schnitt abgeschlossen sind.
II-b)
aaaaaa ∈ M_1 (#(a,w) + #(b,w) = 23)
aaaaaa ∈ M_2 (#(a,w) + 2#(b,w) = 3*2)
aaaaaa not ∈ M_3 (#(a,w) ≠ #(b,w) )
Beweis fertig
das pumping lemma ist nicht konstruktiv !!
d.h. man kann nicht sagen:
wenn das pumping lemma gilt also |x|>= n und x aus L und |v|>=1 und |uv|<=n, dann ist eine sprache regulär !! das geht nicht
man kann nur sagen:
wenn das pumping lemma für reg sprachen nicht gilt, dann ist die untersuchte sprache auch nicht regulär
ich schrieb nur das L(1,n) das Pumping Lemma erfüllt, nicht das daraus folgt, das sie regulär ist!
(genau lesen! rumpöbel)
Warum? Bitte klärung, wenn ihr das nicht durch pumpen zum platzen gebracht habt, stehe ich auf dem Schlauch.
Hat auch wer eine plausible Antwort zu I-5? Ich meine eine Touringmaschine ohne Programm ist führt doch eigentlich die Identitätsfunktion aus, oder?
g Diese Argumentation muss man sich mal auf der Zunge zergehen lassen. Was dann alles regulär währe träum.
Für 0^n1^n bräucht ich sogar nur n Zustände 
nix für ungut
genau, so kann man da auf keinen fall argumentieren
die I-2-a beweisst ihr so wie folgt?
#a + #b = 2n => #a = 2n-#b
#a + 2#b = 3n
(mittels #a einsetzen)
2n-#b+2#b=3n
2n+#b=3n
#b=n
(#a=2n-b# => #a=2n-n=n)
==> #a=#b=n