Fachrat Informatik - Forum

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.

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.

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....

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.

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

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.

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.

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

@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

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?

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.

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.

Mit den zwei Sätzen im Kopfe, ist das in meinen Augen mit einem NEA getan.

okay, habe nochmal nachgedacht.

hast gewonnen.

und danke.

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).

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.

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.

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