04_2003

Archiv Komplexität von Algorithmen
1

wer macht mit?

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.

2

04_2003
i-1

L1=a*; L2=b*;
=> (L1L2)* = (a|b)* ≠ ab = (L1)(L2);

i-2

D({a,b}, {s0,s1,s2}, s0,d,s2)
d = {(s0,a->s1)(s1,b->s2)(s2,a->s1)};

i-3

kann man hier davon ausgehen, dass das normale pumplemma bewiesen ist? dann gehts doch einfach mit:

∃ (ab^ic ∈ L, n∈N) mit |ab|<n, |b|>0
=> wähle a=xu, b=wz => p mit n-l(x)

geht das so mit noch n bissi erklärung und so?

3

zu Pumping Lemma:
Ich überleg immer ob die da eine Abwandlung von dem Beweis im Schöning haben wollen - die machen das da indem sie sagen man kann einen DFA so basteln dass es klappt oder so - aber den Beweis hab’ ich halt irgendwie zwischen den Zeilen noch nicht gefunden…(S 40 ganz oben)

4

Mich würde Aufgabe I-5 interessieren.
Dass die Sprache der Doppelwörter ww w∈Σ* nicht regulär ist, ist mit dem Pumplemma leicht gezeigt. Kontextfreiheit konnt ich aber nicht nachweisen, da ja ich keine kontextfreie Grammatik dazu angeben konnte. Eine kontextsensitive Grammatik ist mir auch nicht eingefallen. Kann jemand von ww zeigen, dass es von einem LBA akzeptiert wird, oder auch nicht?

Zum Pumplemma: ich denke die Zurückführung auf das Ursprüngliche Pumplemma geht so, aber vielleicht will Herr Müller den kompletten Beweis → zurückführen auf normales Pumplemma und dieses dann beweisen (ist ja nicht schlimm). Jedenfalls denk ich, dass nur die Zurückführung alleine keine 7 Punkte wert ist.

5

stimmt das mit dem Beweis eigentlich so wie ich das geschrieben habe? weil irgendwie kommt mir das zu wenig(mathematisch) vor…
Wenn nicht, dann schreibt doch bitte wie’s richtig geht…

6

Hier hab ich eine Grammatik für die ww Sprache - da wäre ich aber in der Klausur sicher nicht darauf gekommen. (Aufgabe 6.2)
http://www.informatik.uni-hamburg.de/TGI/lehre/vl/WS0102/F3/F3loes6.pdf

Zur Regularität: Ich hab es mit dem Pump-Lemma für kontextfreie Sprachen gemacht - da kommt raus, dass sie Sprache nicht kontextfrei ist, also kann sie nach Chomsky auch nicht regulär sein. Bleibt also nur noch Typ 1 oder 0. Aber da weiß ich auch nicht weiter. :-/

7

noch n paar ergebnisse:

iii-6
d=51

iii-3

  1. 41 mod 45
  2. gibts nix

iii-4
kann das jemand gestätigen:

lim √n / 2^√logn ^= lim log√n / √logn = lim 1/2n * 2n*√logn =

lim √logn = infinity ⇒ √n wächst stärker = langsamer

8

Aufgabe I-5
Ist eigentlich nicht so schwer:
Man muss nur die Mitte finden, diese markieren und dann
buchstabenweise vergleichen.
Das könnte man z.B. so machen, dass man immer das linke
Zeichen durch ein anderes ersetzt (a durch A) und das rechte
Zeichen auch. Im nächsten Schritt nimmt man wieder das erste
Zeichen links - das noch nicht durch seinen Grossbuchstaben
ersetzt wurde - und ersetzt dieses und so weiter…
Wenn sich beide Grossbuchstaben treffen, hat man die Mitte
gefunden und ab da isses dann eh einfach.

9

Das war btw Aufgabe 8 in der Übung!
Wenn √n stärker wächst, dann kann aber aber doch nicht besser sein? Da hätte er größere Laufzeit. Man sollte noch den Breakeven point ausrechnen - der liegt bei 2^4 = 16

10

ehrlich gesagt waere ich nicht nur nicht darauf gekommen, sondern ich verstehe die grammatik auch nach anschauen nicht.

aber dabei ist mir noch eine sache aufgefallen: wie ist ein lba definiert?
in diesen folien von der uni hh steht, dass man eine konstante c festlegen muss und die turingmaschine dann nur auf c*|w| operiert. im schoening (s. 84) steht, dass lbas spezielle turingmaschinen sind, die den teil des bandes, auf dem die eingabe steht, nie verlassen.
wer hat recht?

11

Das war btw Aufgabe 8 in der Übung!
Man sollte noch den Breakeven point ausrechnen - der liegt bei 2^4 = 16

12

nichtdeterministisch ist es eigentlich ganz leicht>

s,a/b → A1/B1,,R
s,y → Ch,y,R
A1/B1,a/b → A1/B1,a/b,R
A1/B1,ε → A2/B2,ε,R
A2/B2,a/b-> Rev,y,L
Rev,a/b/y → Rev,a/b/y,L
Rev, → s.,R
Ch,a/b → FALSE,a/b,N
Ch,y → Ch,y,R
Ch, → TRUE,_,N

Naja ok so leicht doch nicht.
Kurze Erklaerung: merkt sich 1. Buchstaben, geht nach rechts, irgendwann nimmt er an er hat die Mitte, wenn dann der Buchstabe passt mit y ueberschreiben und von vorne. Wenns erste Wort weg, schauen ob vom 2. noch was da ist.

13

Hmm ich habe:

Welches Phi(n) hast Du bei III-3.1?
Bei iii-6 musst Du aufpassen, da der ggT(15,9)=3…

14

Hä?:slight_smile: Schau Dir mal die Def. der Chomsky Hierarchie an. Da steht: alle Sprachen sind vom Typ 0. Weiter hinten steht: die durch einer Turingmaschine erkennbaren Sprachen sind genau vom Typ 0. Damit ist wohl die Turing-akzeptierbarkeit für jede Sprache erfüllt :finger:

15

Du meinst III-3.1 richtig?
Die hab ich auf ein 5 mod 9 und ein 1 mod 5 runtergebrochen

16

also iii-6
im skript gibts da 2 methoden: einmal mit primzahl und einmal mit primzerlegung. ich hab (dummerweise) einfach angenommen, phi=377-1…

iii-3
denk ich is doch meins richtig, da 26=11mod15 aber 26 ≠ 4mod9
ich hab auch auf 4mod9 und 1mod5 reduziert und kgV(9,5)=45
ergo: 41mod45 (haut auch mit 86 und -4 hin…)

17

Sorry, betrachtet diesen Beitrag von mir bitte NICHT, ist nämlich falsch! Alle Grammatiken sind automatisch vom Typ 0, nicht alle Sprachen. Sorry nochmals.

18

Etwas genauer formuliert: Im Skript gibt es zwei Methoden: Einmal die mit Primzahl, und einmal das RSA-Verfahren = Primfaktorzerlegung. In der Aufgabenstellung steht es schon drin, dass es sich um ein RSA-Verfahren handelt - also der Tip vom Strehl :wink: