Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in END-AF

Beantwortet: verstandnis für v

Fri, 21 Jan 2022 16:51:51 +0000

Hallo,

ich bin mir nicht ganz sicher, ob ich die Frage richtig verstanden habe, falls nicht, frage einfach noch einmal und konkretisiere die Frage am besten.

Da in b) kein v vorkommt, geht es vermutlich um a). Alle Wörter, die am Ende auf abc Enden, gehören zur Sprache. Das heißt, es ist egal, wie das Wort am Anfang aussieht, v besteht aus a,b,c in beliebiger Reihenfolge und Häufigkeit und dann sind alle Wörter, die dazugehören vabc

Beantwortet: Alternative Lösung des zugehörigen regulären Ausdruckes

Fri, 27 Dec 2019 20:14:11 +0000

Hallo,

das geht so leider nicht, da du mit dem Sternoperator bewirkst, dass der Inhalt der Klammer auch 0-mal wiederholt werden kann. Dann wär die Bedingung nicht erfüllt.

Viele Grüße

Niklas (Tutor)

Beantwortet: Weitere Lösung

Sun, 12 Feb 2017 10:54:59 +0000

Sie können Wörter vom Typ $0~11110~111$ nicht ableiten. Das heißt, Wörter, wo nach mehr als drei Einsen wieder eine Null kommen soll.

Wörter der Sprache starten mit $0$ und enden mit $111$, wobei dazwischen alle möglichen Kombinationen aus Nullen und Einsen vorkommen können müssen.

Beantwortet: Aufgabe 9a) Automat Pfeile

Wed, 27 Jan 2016 07:20:34 +0000

Hallo,

die Aufgabe ist hier ein EA zu erstellen, der alle beliebigen Wörter mit der Endung abc akzeptiert. Angenommen es wurde ein a gelesen, und anschließend kommt ein c, der Pfeil würde auf s1 zeigen, dann würde der Automat auch ein Wort akzeptieren, das cbc zum Schluss hätte (der "a"-Pfeil geht ja auf s1 zurück).
Gleiches gilt für s2: wenn ein "a" gelesen wurde, kommt man in s2. Kommt nun ein "a" und man bliebe in s2 würde der Automat ein Wort akzeptieren das als Ende "abac" hätte, dies ist in der Aufgabenstellung ausgeschlossen.

Der Grund hier also wieso immer wieder zurück gegangen wird, bedeutet man ist in s1, es kommt ein "a", dann kann man in s1 bleiben, da man mit einem "a" davor auch in s2 gekommen ist. Schreibt man nun ein "b" ist man in s2. Wenn nun etwas anderes als ein "c" kommt muss man in den Zustand zurück, sodass man insgesamt mit einer "abc"-Endung in s3 kommt. Bedeutet bei einem "a" zurück zu s1, da man mit einem "a" in s1 gelandet ist, und mit einem "b" wieder zurück zu s0 da man von Vorne anfangen muss (vor dem "b" muss ein "a" stehen, in diesem fall würde da allerdings ein "b" stehen).

Ich hoffe es wird so etwas klarere :)
Viele Grüße,

Marc (Tutor)

Beantwortet: Verständnis zur Lösung von Teil b)

Wed, 15 Oct 2014 17:06:07 +0000

Es ist am geschicktesten, wenn du den Potenzmengenalgorithmus zur Umwandlung in einen deterministischen Automaten benutzt.

Um die unzulässige 1 am Anfang abzufangen wird ein Sackgassenzustand hinzugefügt, der kein Endzustand ist. Dieser Zustand repräsentiert die leere Menge.

Christoph (Tutor)

Beantwortet: Alternativlösung zu Teil b)

Wed, 15 Oct 2014 16:59:39 +0000

Bei dieser Aufgabe steht halt explizit dabei, dass man die Sprache formal angeben soll, daher wäre Ihre Lösung genau genommen nicht korrekt.

In der Klausur verlangen wir meistens aber nicht unbedingt eine formale Lösung, sondern stellen es Ihnen frei, ob Sie eine formale Beschreibung angeben oder eine PRÄZISE umgangssprachliche. In diesem Fall wäre Ihre Lösung in Ordnung.

Ich möchte dazu aber betonen, dass es bei komplizierteren Sprachen meist sehr viel einfacher (also kürzer) ist, eine formale Definition anzugeben, als umgangssprachlich alle Eigenschaften anzugeben. Es lohnt sich also, das ein wenig zu üben, um es in der Klausur zu beherrschen.

Viele Grüße

Lukas König und Friederike Pfeiffer-Bohnen

Beantwortet: Alternativer endlicher Automat

Wed, 15 Oct 2014 16:57:18 +0000

Hallo,

was mir bei deinem EA aufgefallen ist: Eigentlich soll sich der Zustand s1 ja merken, dass unser letztes Zeichen ein "a" gewesen ist. Wenn ich jetzt noch ein "a" eingebe, ist mein letztes eingegebenes Zeichen aber immer noch ein "a". Anders gesagt: Wie könnte das Wort weitergehen, damit wir im Endzustand landen? Nun, wir könnten z.B. bc dranhängen, oder aber wir hängen "abc" dran, denn das ändert nichts daran, dass unser Wort weiterhin auf abc endet.

Bei dir würde man aber bei der Eingabe von a im Zustand s1 wieder zurück im Startzustand landen. Konkret bedeutet dies, dass dein EA das Wort "aabc" zum Beispiel nicht akzeptieren kann, obwohl es Teil der Sprache ist. Damit wäre dein EA nicht äquivalent zum EA in der Musterlösung.

Ich hoffe, ich konnte dir damit weiterhelfen.

Viele Grüße,

Vivian (Tutor)

Beantwortet: Verständnis der Sprachendefinition

Wed, 15 Oct 2014 16:52:49 +0000

In dieser Aufgabe ist es prinzipell egal, ob vorne ein + oder * steht, da hinten mit w=vabc genauer spezifiziert wird, wie das Wort auszusehen hat, es muss nämlich immer auf abc enden, kann also nicht leer sein.

Grundsätzlich muss aus der Beschreibung der Sprache immer hervorgehen, ob das leere Wort enthalten ist oder nicht. Es gibt unterschiedliche Möglichkeiten, die formale Beschreibung der Sprache aufzuschreiben, hier hat man die Wahl, aber das ist eben nicht immer so.

Ich hoffe das ist als Antwort verständlich :)

Viele Grüße,

Melanie (Tutor)

Beantwortet: Alternativer Lösungsvorschlag für den regulären Ausdruck

Wed, 15 Oct 2014 16:48:44 +0000

Das wäre falsch. "Die Abzweigung" von a führt in den Nicht-Endzustand f, aus dem man nicht mehr raus kommt. Heißt also, dass eine Wort, das mit einer 1 beginnt nicht akzeptiert werden kann (dies wäre bei deinem regulären Ausdruck möglich). Man baut ja immer nur die "Wege" durch den Automaten mit dem regulären Ausdruck nach, die in einen Endzustand führen. Dabei ist es meistens leichter, wenn man vom nicht determinstisch Automaten ausgeht.

Sven (Tutor)

Beantwortet: Alternativer regulärer Ausdruck

Wed, 15 Oct 2014 16:46:50 +0000

Hallo,

das Problem bei Deinem regulären Ausdruck ist, dass die Wörter immer auf 0111 enden. Das ist aber nicht der Fall. Stattdessen enden alle Wörter der Sprache immer mit mindestens drei einsen.

Beispiel: Das Wort 0111, welches Teil der Sprache ist, lässt sich mit Deinem regulären Ausdruck nicht darstellen, weil der immer mindestens zwei Nullen erzeugt.

Relativ schnell kann man den regulären Ausdruck in der Musterlösung aber auch bei dieser Aufgabe aus dem nicht-deterministischen EA ableiten.

Viele Grüße

Ben (Tutor)

Beantwortet: Alternativer regulärer Ausdruck

Wed, 15 Oct 2014 16:41:33 +0000

Das ist eine alternative Lösung, unsere ist aber auch richtig, denn die beliebig vielen 1en kann man auch mit (0+1)* bekommen.

Viele Grüße

Lukas König