Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

Currywurst mit Pommes

Erfahrener Schreiberling

  • "Currywurst mit Pommes" started this thread

Posts: 438

Date of registration: Oct 14th 2002

41

Wednesday, September 26th 2007, 10:30am

Quoted

Original von Jojo
ich glaube dass in der Vorlesung genau umgekehrt gezeigt wurde (fuer jeden NEA existiert ein DEA)


Und ich steck nicht mehr so drin in ThI, aber ich meine gelesen zu haben, dass NEA und DEA für diesen Fall äquivalent sind.
  • Send private message

Neutrino

masselos

  • "Neutrino" is male

Posts: 661

Date of registration: Oct 6th 2005

Location: Hannover

Occupation: SRA Mitarbeiter

42

Wednesday, September 26th 2007, 1:50pm

Quoted

Original von Currywurst mit Pommes

Quoted

Original von Jojo
ich glaube dass in der Vorlesung genau umgekehrt gezeigt wurde (fuer jeden NEA existiert ein DEA)


Und ich steck nicht mehr so drin in ThI, aber ich meine gelesen zu haben, dass NEA und DEA für diesen Fall äquivalent sind.


Es gibt für jeden NEA einen DEA und natürlich auch andersrum, indem man zur not ein paar epsilon übergänge einbaut, aber ich wüsste nich wozu man den NEA brauchen könnte.
  • Send private message

Paulus

Zuhörer

Posts: 2

Date of registration: Sep 22nd 2007

43

Wednesday, September 26th 2007, 2:48pm

Wir betrachten die Sprache Lnww aller Woerter ueber dem Alphabet {0, 1} ,
die fuer kein w die Form ww haben, also
Lnww = nicht {ww | w aus {0,1}*} .
Zeigen Sie, dass Lnww kontextfrei ist.

Fuer einen Vorschlag wäre ich sehr dankbar....
  • Send private message

Jojo

Trainee

  • "Jojo" is male

Posts: 94

Date of registration: Nov 16th 2005

Location: Foreign Recruit :)

Occupation: Programmierer

44

Wednesday, September 26th 2007, 3:23pm

dazu brauchst du einen Kellerautomat(NKA) Konextfreie Sprachen werden von NKA entschieden
  • Send private message

julianr

Erfahrener Schreiberling

Posts: 298

Date of registration: Oct 13th 2005

Location: I live in a giant bucket.

45

Wednesday, September 26th 2007, 3:45pm

Ja, oder man gibt eine Typ2-Grammatik an. Meine ist aber falsch *bemerk*… Vorschläge? ;)

Und bei KvA, Aufg. 14 ist meine Lösung wohl auch Mist. Ich dachte, man wartet einfach c*t(n) und wenn es dann nicht fertig ist, dann gibt man 0 aus. Aber dass man c kennt, ist ja gar nicht gegeben. Dito für die additive Konstante. *wirr*

This post has been edited 1 times, last edit by "julianr" (Sep 26th 2007, 3:52pm)

  • Send private message

aliaatreides

Praktikant

  • "aliaatreides" is female

Posts: 24

Date of registration: May 3rd 2007

Occupation: 4. Semester Informatik

46

Wednesday, September 26th 2007, 5:48pm

Quoted

Original von julianr
Ja, oder man gibt eine Typ2-Grammatik an. Meine ist aber falsch *bemerk*… Vorschläge? ;)

Und bei KvA, Aufg. 14 ist meine Lösung wohl auch Mist. Ich dachte, man wartet einfach c*t(n) und wenn es dann nicht fertig ist, dann gibt man 0 aus. Aber dass man c kennt, ist ja gar nicht gegeben. Dito für die additive Konstante. *wirr*


warte dann t^2(|w|)! :)
I must not fear. Fear is the mind-killer.
Fear is the little-death that brings total obliteration.
I will face my fear.
I will permit it to pass over me and through me.
  • Send private message

Joachim

Guru

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

47

Wednesday, September 26th 2007, 5:51pm

Quoted

Original von julianr
Und bei KvA, Aufg. 14 ist meine Lösung wohl auch Mist. Ich dachte, man wartet einfach c*t(n) und wenn es dann nicht fertig ist, dann gibt man 0 aus. Aber dass man c kennt, ist ja gar nicht gegeben.
Das spielt keine Rolle. Da es solche Konstanten gibt, gibt es auch einen Algorithmus, der die Simulation mit diesen Konstanten ausführen kann und funktioniert wie Du Dir das gedacht hast. Es geht schließlich nur darum, daß ein solcher Algorithmus existiert.
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962

This post has been edited 1 times, last edit by "Joachim" (Sep 26th 2007, 5:51pm)

  • Send private message

aliaatreides

Praktikant

  • "aliaatreides" is female

Posts: 24

Date of registration: May 3rd 2007

Occupation: 4. Semester Informatik

48

Wednesday, September 26th 2007, 5:51pm

Quoted

Original von Neutrino
IMHO geht das am besten indem man erst nen NEA aufbaut-> DEA ->Grammatik einfach ablesen (siehe Vorlesungsmethode).


Ja, genau! Aber in der Uebung wurde die Grammatik direkt aus dem NEA gelesen (keine DEA durch Potenzmengekonstruktion)... Und die Frage war: ist es auch so richtig?
I must not fear. Fear is the mind-killer.
Fear is the little-death that brings total obliteration.
I will face my fear.
I will permit it to pass over me and through me.
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

49

Wednesday, September 26th 2007, 6:22pm

Ja.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

Neutrino

masselos

  • "Neutrino" is male

Posts: 661

Date of registration: Oct 6th 2005

Location: Hannover

Occupation: SRA Mitarbeiter

50

Wednesday, September 26th 2007, 7:20pm

Quoted

Original von aliaatreides

Quoted

Original von Neutrino
IMHO geht das am besten indem man erst nen NEA aufbaut-> DEA ->Grammatik einfach ablesen (siehe Vorlesungsmethode).


Ja, genau! Aber in der Uebung wurde die Grammatik direkt aus dem NEA gelesen (keine DEA durch Potenzmengekonstruktion)... Und die Frage war: ist es auch so richtig?


ach so, dann hatte ich deine Frage nich richtig verstanden. Ich glaub, wenn nich explizit dasteht, wie dus machen sollst, kannst du sicher auch den schritt mit DEA weglassen.

This post has been edited 1 times, last edit by "Neutrino" (Sep 26th 2007, 7:21pm)

  • Send private message

Jojo

Trainee

  • "Jojo" is male

Posts: 94

Date of registration: Nov 16th 2005

Location: Foreign Recruit :)

Occupation: Programmierer

51

Wednesday, September 26th 2007, 8:25pm

Zeigen Sie: Es gibt Sprachen A und B, sodass folgendes gilt: A und B
koennen von Kellerautomaten erkannt werden, aber es gibt keinen Kellerautomaten,der A vereinigt B erkennt.

Wie kann man so was zeigen?
  • Send private message

julianr

Erfahrener Schreiberling

Posts: 298

Date of registration: Oct 13th 2005

Location: I live in a giant bucket.

52

Wednesday, September 26th 2007, 8:36pm

Zwei Sprachen angeben, für die es trivialerweise einen Kellerautomaten gibt, und bei der Vereinigung per Pumpen zeigen, dass es nicht klappt.

This post has been edited 1 times, last edit by "julianr" (Sep 26th 2007, 8:37pm)

  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

53

Wednesday, September 26th 2007, 8:38pm

Überlege dir zwei Sprachen, die jeweils kontextfrei sind (indem du jeweils z. B. eine kontextfreie Grammatik angibst oder Kellerautomaten) und dann mit dem uvwxy-Pumping-Lemma zeigst, dass der Schnitt der beiden Sprachen nicht mehr kontextfrei ist.

Edit: ich sehe, es war jemand schneller ;).
Edit2: in deiner Aufgabe ging es darum zu zeigen, dass die Vereinigung nicht kontextfrei ist. Das ist aber falsch, da kontextfreie Sprachen unter Vereinigung abgeschlossen sind. Es gilt nur nicht für den Schnitt.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

julianr

Erfahrener Schreiberling

Posts: 298

Date of registration: Oct 13th 2005

Location: I live in a giant bucket.

54

Wednesday, September 26th 2007, 9:06pm

Krieg ich dafür einen Tipp für Lnww? ;)
  • Send private message

Dot

Senior Schreiberling

Posts: 618

Date of registration: Feb 3rd 2003

Location: Ex-Europameisterland

Occupation: 4TheScience

55

Wednesday, September 26th 2007, 9:09pm

Ich hab mich heut mal beim Problemlösen gefilmt
http://youtube.com/watch?v=vi7He4GfUkg

Ach, was vernünftiges habe ich auch noch beizutragen:
Mal angenommen es kommt so ne Aufgabe ähnlich der Aufgabe 17, aber mit den kontextsensitiven Sprachen, anstatt den Kontextfreien. Diese Werden ja von einer LBA erkannt. Nehm ich dann beim Transfer eine Mehrband-TM die rechts und links beschränkt ist oder wie mache ich das? Als nur KvAler-Schreiber fehlen mir leider bisschen die GtI Kenntnisse :D
C:\reality.sys has errors - Reboot the universe? (Y/N)

Real programmers don't comment their code.
It was hard to write, it should be hard to understand

This post has been edited 1 times, last edit by "Dot" (Sep 26th 2007, 9:45pm)

  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

56

Wednesday, September 26th 2007, 9:53pm

Quoted

Original von julianr
Krieg ich dafür einen Tipp für Lnww? ;)

Wie wärs mit Wortmitte raten?

Edit: ah hab das "nicht" überlesen. Da geht's dann natürlich nicht mit Wortmitte raten ;)
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

julianr

Erfahrener Schreiberling

Posts: 298

Date of registration: Oct 13th 2005

Location: I live in a giant bucket.

57

Thursday, September 27th 2007, 12:27am

Hm… … …naja, muss ich die Klausur wohl ohne Lnww schaffen *block* ;)

This post has been edited 1 times, last edit by "julianr" (Sep 27th 2007, 12:28am)

  • Send private message

Hazel

Praktikant

  • "Hazel" is male

Posts: 21

Date of registration: Jan 10th 2006

58

Thursday, September 27th 2007, 7:50am

@Julien: Ich hab die so gelöst:

1. Schauen ob gerade Anzahl Zeichen, falls nein: ablehnen. Ansonsten: Erstes Zeichen finden, dass nach dem Trennsymbol kommen würde
2. Erstes Zeichen ganz links markieren
3. Nach Rechts laufen
4. Zeichen markieren, aber mit einem anderen Symbol(ich habe Striche über und unter den Zeichen verwendet..)
5. Solange wiederholen bis 2 verschiedene Markierungen aufeinander treffen
6. Das Trennzeichen käme vor dem ersten rechten Markierungssymbol nach dem der linken.

Hoffe das ist verständlich... ich wurde grad aus dem Bett geklingelt und hatte noch keinen Kaffee.. *gg*
Think positive. Think big.

This post has been edited 3 times, last edit by "Hazel" (Sep 27th 2007, 7:52am)

  • Send private message

Dot

Senior Schreiberling

Posts: 618

Date of registration: Feb 3rd 2003

Location: Ex-Europameisterland

Occupation: 4TheScience

59

Thursday, September 27th 2007, 9:28am

So, dann mal viel Erfolg allen, cu@uni
C:\reality.sys has errors - Reboot the universe? (Y/N)

Real programmers don't comment their code.
It was hard to write, it should be hard to understand
  • Send private message

Jessie

Unregistered

60

Thursday, September 27th 2007, 9:32am

Ich wünsche Euch auch allen viel Erfolg!!
(Nächstes Semester schreib ich dann auch mal...)

@Janni: TSCHAKKKKKKKKKAAAAAAAAAAA!!!!!!!!!!!!!!
:D