You are not logged in.

Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

141

Saturday, February 28th 2004, 3:47pm

ja schön joka, die lösungen sind ähnlich aber nicht gleich

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

142

Saturday, February 28th 2004, 3:50pm

Quoted

Original von Uprooter
eigentlich wollt ich wissen, ob man das arbeitsalphabet selbst wählen darf?
Das Arbeitsalphabet kan man natürlich frei wählen, solange die TM wie in Abschnitt 5 des Skripts definiert wird.

Entscheidend ist ja nur, daß die TM genau die Wörter der Sprache akzeptiert.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

143

Saturday, February 28th 2004, 3:52pm

Quoted

Original von Uprooter
eine verständnisfrage zum kellerautomaten:
wenn ich im laufe des lesens vom wort den keller immer wieder löschen und neu beschreiben möchte, überschreibe ich dann einfach das letzte zeichen mit #, also zB z5 b B->z6#(wenn B das letzte zeichen)?
Das kannst Du machen wie Du möchtest. Nur komplett löschen darfst Du den Keller nicht, da er sonst anhält (es sei denn, dies ist gewollt). Siehe dazu Abschnitt 4.1 im Skript.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Mutzkow

Junior Schreiberling

  • "Mutzkow" is male

Posts: 129

Date of registration: Oct 10th 2003

Location: Hannover

Occupation: Informatik

144

Saturday, February 28th 2004, 3:52pm

Hier is ein Prog, das mal ganz interessant sein könnte:

http://www.num.math.uni-goettingen.de/vl…terial/SIMA.zip

Kann scheinbar Turing-Maschinen, Kellerautomaten usw. usw...
Damit kann man wohl recht gut kontrollieren, ob der selbst kreierte Kellerautomat usw. funzt....
Es ist ein einförmiges Ding um das Menschengeschlecht. Die meisten verarbeiten den größten Teil der Zeit, um zu leben, und das bisschen, das ihnen von Freiheit übrig bleibt, ängstigt sie so, dass sie alle Mittel aufsuchen, um es los zu werden.

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

145

Saturday, February 28th 2004, 3:54pm

Quoted

Original von Lucky
Kannste mal n Tipp geben, bzw würde es noch Punkte dafür geben, trotz der kleinen Hilfsmaßnahme?
Da Du einen Kellerautomat zu einer anderen Sprache konstruieren würdest als verlangt war, gibt es da mit Sicherheit nur wenige bis gar keine Punkte drauf.

Wie bereits erwähnt, ist ja gerade der Trick an der Sache, daß man einen nichtdeterministischen Kellerautomaten verwendet.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

JoKa

Trainee

  • "JoKa" is male

Posts: 46

Date of registration: Dec 30th 2002

Location: Hannover

146

Saturday, February 28th 2004, 3:56pm

Quoted

Original von Uprooter
ja schön joka, die lösungen sind ähnlich aber nicht gleich


Sorry, aber ich kann keinen Unterschied erkennen.

Gruss JoKa

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

147

Saturday, February 28th 2004, 3:57pm

Quoted

Original von Mutzkow
Öhm, also da find ich diese Raterei leicht unfruchtbar irgendwie so...

Ich mein, rumraten als Lösung für so ne Aufgabe?
Naja, "raten" ist ja nur eine Erklärungsweise für das Verhalten nichtdeterministischer Kellerautomaten.

Man könnte es auch so verstehen, daß nichtdeterministische Kellerautomaten einfach alle möglichen Berechnungswege durchprobieren und genau dann akzeptieren, wenn einer dieser Berechnungswege erfolgreich ist.

Das "raten" wäre dann die Sichtweise, daß der Kellerautomat immer automatisch einen akzeptierenden Rechenweg einschlägt, wenn es denn einen gibt.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

This post has been edited 1 times, last edit by "Joachim" (Feb 28th 2004, 4:00pm)


  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

148

Saturday, February 28th 2004, 4:02pm

Quoted

Original von Mutzkow
Hier is ein Prog, das mal ganz interessant sein könnte:

http://www.num.math.uni-goettingen.de/vl…terial/SIMA.zip

Kann scheinbar Turing-Maschinen, Kellerautomaten usw. usw...
Damit kann man wohl recht gut kontrollieren, ob der selbst kreierte Kellerautomat usw. funzt....
Darauf sollte man sich nicht verlassen. Turing-Maschinen und Kellerautomaten lassen sich auf verschiedene (aber äquivalente) Weisen definieren. Das Verhalten der Automatenmodelle aus der Vorlesung kann also (und wird wahrscheinlich auch) von dem Verhalten der Modelle aus dem Programm abweichen.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

This post has been edited 1 times, last edit by "Joachim" (Feb 28th 2004, 4:05pm)


Mutzkow

Junior Schreiberling

  • "Mutzkow" is male

Posts: 129

Date of registration: Oct 10th 2003

Location: Hannover

Occupation: Informatik

149

Saturday, February 28th 2004, 4:13pm

Quoted

Original von Joachim

Quoted

Original von Mutzkow
Hier is ein Prog, das mal ganz interessant sein könnte:

http://www.num.math.uni-goettingen.de/vl…terial/SIMA.zip

Kann scheinbar Turing-Maschinen, Kellerautomaten usw. usw...
Damit kann man wohl recht gut kontrollieren, ob der selbst kreierte Kellerautomat usw. funzt....
Darauf sollte man sich nicht verlassen. Turing-Maschinen und Kellerautomaten lassen sich auf verschiedene (aber äquivalente) Weisen definieren. Das Verhalten der Automatenmodelle aus der Vorlesung kann also (und wird wahrscheinlich auch) von dem Verhalten der Modelle aus dem Programm abweichen.


Ich weiss nicht genau, was du da meinst mit unterschiedlichen Definitionen, aber bin eh dazu geneigt, dir lieber nicht zu widersprechen ;)
Es ist ein einförmiges Ding um das Menschengeschlecht. Die meisten verarbeiten den größten Teil der Zeit, um zu leben, und das bisschen, das ihnen von Freiheit übrig bleibt, ängstigt sie so, dass sie alle Mittel aufsuchen, um es los zu werden.

Mutzkow

Junior Schreiberling

  • "Mutzkow" is male

Posts: 129

Date of registration: Oct 10th 2003

Location: Hannover

Occupation: Informatik

150

Saturday, February 28th 2004, 5:27pm

@Joachim

Du hattest mal in einer Übung die Lösung zu Blatt 6 angegeben. Bei der Aufgabe 1 hast du die zwei Wörter in 7 verschiedene Bereiche aufgeteilt und dann jeweils pro Bereich versucht, ob das vwx in einem dieser Bereiche zu finden ist, sodass das PL gilt.

Frage: Wenn bereits in der Untersuchung in den Bereichen 1-4 bewiesen ist, dass das Pumping Lemma NICHT gilt, wieso betrachtest du dann die anderen Bereiche noch mal? Weil ich hatte das bisher so verstanden: Beim PL schaut man sich einen Sonderfall der Sprache an und schließt damit auf die Allgemeinheit. Konkret: Du bringst anhand eines konkreteren Beispiels, wie du zB bei o.g. Aufgabe mit a^n b^n a^n b^n gemacht hast (das ist ja ein Sonderfall der angegebenen Sprache) die Annahme, die Sprache ist von Typ 2 zum Widerspruch und hast somit bewiesen, dass es für die Sprache Sonderfälle gibt, die nicht vom Typ 2 sind.

OK, jetzt hab ich total wirr geschrieben :(
Frage war eigentlich: Warum hast du so viele Fallunterscheidungen in der o.g. Sprache gewählt? Reicht es nicht, dassu das PL auf nur EINEN Bereich anwendest, zu nem Widerspruch führst und das wars?

Danke übrigens, dassu dich hier so nett um uns Ersis kümmerst :)

Gruß,
Mutzkow :)
Es ist ein einförmiges Ding um das Menschengeschlecht. Die meisten verarbeiten den größten Teil der Zeit, um zu leben, und das bisschen, das ihnen von Freiheit übrig bleibt, ängstigt sie so, dass sie alle Mittel aufsuchen, um es los zu werden.

Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

151

Saturday, February 28th 2004, 6:10pm

meinen dank hast du natürlich auch :D

Krebskasper

Praktikant

  • "Krebskasper" is male

Posts: 24

Date of registration: Dec 18th 2003

Location: Mutterns Bauch

Occupation: Mathe / Inf

152

Saturday, February 28th 2004, 7:38pm

folgendes:

ich lerne unter anderem mit einem der 2 bücher, die von prof. vollmer empfohlen wurde.
da steht, dass per def. eine sprache regulär ist, wenn sie durch einen endlcihen automaten dargestellt werden kann (DEA, NEA oder NEA/epsilon)

im skript steht dasselbe, nur dass die def. auf einen DEA beschränkt ist.

kann ich in der klausur trotzdem die erste definition benutzen?

Informatik Minister

Senior Schreiberling

  • "Informatik Minister" is male

Posts: 1,234

Date of registration: Dec 11th 2001

153

Saturday, February 28th 2004, 8:19pm

Quoted

Original von Krebskasper
da steht, dass per def. eine sprache regulär ist, wenn sie durch einen endlcihen automaten dargestellt werden kann (DEA, NEA oder NEA/epsilon)

im skript steht dasselbe, nur dass die def. auf einen DEA beschränkt ist.


Hi,

zu jedem nicht deterministischen endlichen Automaten mit epsilon-Übergängen kann man einen äquivalenten NDEA konstruieren, der die gleiche Sprache akzeptiert. Für diesen NDEA kann wiederum ein DEA konstruiert werden.
Kommt also aufs Gleiche hinaus.
"Fliegenpilze! Löwen!! Das Leben ist gefährlich." -- www.katzundgoldt.de

Krebskasper

Praktikant

  • "Krebskasper" is male

Posts: 24

Date of registration: Dec 18th 2003

Location: Mutterns Bauch

Occupation: Mathe / Inf

154

Saturday, February 28th 2004, 8:32pm

stimmt.

aber wenn ich in der klausur beweisen soll, dass eine sprache regulär ist, dann ist es am einfachsten einen NEA oder einen NEA/epsilon automaten zu entwerfen.

Informatik Minister

Senior Schreiberling

  • "Informatik Minister" is male

Posts: 1,234

Date of registration: Dec 11th 2001

155

Saturday, February 28th 2004, 9:20pm

Mit den zwei Sätzen im Kopfe, ist das in meinen Augen mit einem NEA getan.
"Fliegenpilze! Löwen!! Das Leben ist gefährlich." -- www.katzundgoldt.de

Krebskasper

Praktikant

  • "Krebskasper" is male

Posts: 24

Date of registration: Dec 18th 2003

Location: Mutterns Bauch

Occupation: Mathe / Inf

156

Saturday, February 28th 2004, 9:26pm

okay, habe nochmal nachgedacht.

hast gewonnen.

und danke.

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

157

Sunday, February 29th 2004, 11:31am

Quoted

Original von Mutzkow
@Joachim

Du hattest mal in einer Übung die Lösung zu Blatt 6 angegeben. Bei der Aufgabe 1 hast du die zwei Wörter in 7 verschiedene Bereiche aufgeteilt und dann jeweils pro Bereich versucht, ob das vwx in einem dieser Bereiche zu finden ist, sodass das PL gilt.

Frage: Wenn bereits in der Untersuchung in den Bereichen 1-4 bewiesen ist, dass das Pumping Lemma NICHT gilt, wieso betrachtest du dann die anderen Bereiche noch mal? Weil ich hatte das bisher so verstanden: Beim PL schaut man sich einen Sonderfall der Sprache an und schließt damit auf die Allgemeinheit. Konkret: Du bringst anhand eines konkreteren Beispiels, wie du zB bei o.g. Aufgabe mit a^n b^n a^n b^n gemacht hast (das ist ja ein Sonderfall der angegebenen Sprache) die Annahme, die Sprache ist von Typ 2 zum Widerspruch und hast somit bewiesen, dass es für die Sprache Sonderfälle gibt, die nicht vom Typ 2 sind.

OK, jetzt hab ich total wirr geschrieben :(
Frage war eigentlich: Warum hast du so viele Fallunterscheidungen in der o.g. Sprache gewählt? Reicht es nicht, dassu das PL auf nur EINEN Bereich anwendest, zu nem Widerspruch führst und das wars?
Um zu zeigen, daß das Pumping Lemma nicht gilt, müssen wir beweisen, daß es keine Zerlegung uvwxy gibt, die die drei Bedingungen des Pumping Lemmas erfüllt. Da wir aber nicht wissen, in welchem Bereich des Wortes x = a^n b^n a^n b^n das Teilwort uvw liegt, müssen wir für alle Bereiche, in denen es liegen könnte, zeigen, daß es dort nicht liegt (also einen Widerspruch erzeugen). Entweder besteht uvw nur aus "a"s und "b"s (Fälle 1 bis 4) oder uvw besteht sowohl aus "a"s als auch aus "b"s (Fälle 5 bis 7).
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

158

Sunday, February 29th 2004, 11:32am

Quoted

Original von Krebskasper
ich lerne unter anderem mit einem der 2 bücher, die von prof. vollmer empfohlen wurde.
da steht, dass per def. eine sprache regulär ist, wenn sie durch einen endlcihen automaten dargestellt werden kann (DEA, NEA oder NEA/epsilon)

im skript steht dasselbe, nur dass die def. auf einen DEA beschränkt ist.

kann ich in der klausur trotzdem die erste definition benutzen?
Endliche Automaten (egal, welcher speziellen Art) sind das Äquivalent zu regulären Grammatiken. Das gilt aber nicht per Definition, sondern läßt sich beweisen. Beide Modelle zur Beschreibung von Sprachen sind also absolut gleichwertig.

Demnach erkennt jeder endliche Automat eine reguläre Sprache. Und jede reguläre Sprache ist von einen endlichen Automaten erkennbar.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

159

Sunday, February 29th 2004, 11:33am

Quoted

Original von Krebskasper
aber wenn ich in der klausur beweisen soll, dass eine sprache regulär ist, dann ist es am einfachsten einen NEA oder einen NEA/epsilon automaten zu entwerfen.
Automaten mit Epsilon-Übergängen haben wir in der Vorlesung nicht behandelt. Daher solltest Du solche Automaten in der Klausur lieber vermeiden.

Aber Du kannst davon ausgehen, daß Du in der aktuellen Klausur einen NEA mit Epsilon-Übergängen nicht sinnvoll verwenden können wirst. :)
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

This post has been edited 1 times, last edit by "Joachim" (Feb 29th 2004, 11:34am)


NullAhnung

Erfahrener Schreiberling

  • "NullAhnung" is female

Posts: 332

Date of registration: Apr 28th 2003

160

Sunday, February 29th 2004, 12:34pm

Kann man für eine kontextfreie Sprache auch sowas erzeugen:
S->e, aXbX (?)
X-> ab, aXb´

?( ?(