Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität in AU-2-3

Kommentiert: optionales Übungsblatt 2, Aufgabe 8

Sat, 08 Jan 2022 09:07:17 +0000

Alles Klar
Vielen Dank

Beantwortet: Fehlerhafte Lösung?

Fri, 09 Feb 2018 07:59:58 +0000

Hallo,

den Lambda-Übergang kannst du immer verwenden, sobald der Zustand und der Keller stimmt, da du das Leere Wort quasi überall einfügen kannst (deshalb muss man hier auch immer bei deterministischen Automaten aufpassen).

Wie du dann richtig erkannt hast, kann man so wieder zurück zum Anfang und das Wort weiter bearbeiten.

Viele Grüße

Youri (Tutorin)

Erneut kategoriesiert: Übung 2 Nr 5 - Lösung

Mon, 18 Dec 2017 13:14:08 +0000

Hallo

Kann es sein dass die Lösung fehlerhaft ist?

Es ist doch garkein Übergang für (s1,0,k0) definiert, wie kann man dann die Sprache und insbesondere das Testwort so ableiten?

Antwort bearbeitet: Konfigurationsfolge lambda-Übergang

Thu, 05 Jan 2017 12:10:51 +0000

Hallo,

bei einem Kellerautomaten und dessen Zustandsübergängen, hat lambda auf der rechten und linken Seite der Definition eine unterschiedliche Bedeutung. Die beiden Seiten sind wie folgt aufgebaut (Der Zustand in dem sich der Kellerautomat befindet, das Zeichen das der Lesekopf einliest, das oberste Kellerzeichen) --> (Der Zustand in den der Kellerautomat wecheselt, die Operation die der Kellerautomat auf dem Keller ausübt). Bei den markierten Wechseln in der Konfigurationsfolge handelt es sich um folgenden Übergang: (s1,λ,k0) →(s0,k0) dieser besagt, dass der Lesekopf auf dem Zeichen auf dem er sich momentan befindet stehen bleibt (λ) und der Kellerautomat ledeglich den Zustand von s1 in s0 wechselt, ohne das sich der Lesekopf ein Zeichen nach rechts bewegt bzw. eine Operation auf dem Keller ausübt.

Viele Grüße
Timo (Tutor)

Kommentiert: Unterschied Deterministischen und Nichtdeterministischen Kellerautomaten?

Tue, 02 Feb 2016 16:25:23 +0000

Wieso ist denn bei Tut 2 auf Folie 17 der Kellerautomat trotz Lambda-Übergang deterministisch ?

Kommentiert: Hat s0 einen Sonderstatus?

Tue, 02 Feb 2016 16:21:53 +0000

Wie erkenne ich denn das s0 mein Endzustand ist ?

Beantwortet: Wie kann ich mit Hilfe des XWizards reguläre Ausdrücke vergleichen?

Mon, 18 Jan 2016 08:06:06 +0000

Tja, leider kann das der XWizard noch nicht. Es gibt noch einige (viele!) Funktionen, die ich gerne einbauen würde, für die ich aber bisher keine Zeit hatte. Dazu gehören vor allem auch Funktionen rund um die regulären Ausdrücke.

Was ich plane, ist folgendes: Man soll reguläre Ausdrücke in endliche Automaten umwandeln können (bisher geht ja nur das Umgekehrte). Diese kann man ja dann deterministisch machen und minimieren. Wenn man das mit zwei verschiedenen regulären Ausdrücken macht, kann man am Ende vergleichen, ob derselbe Automat herauskommt. Mal sehen, ob ich das noch in diesem Semester schaffe...

Was die angegebenen beiden Ausdrücke angeht: die sind beide äquivalent und definieren die Sprache mit mindestens einer 1. Ihr eigener Ausdruck ist sogar kürzer als unsere Lösung (dafür ist diese ein bisschen intuitiver).

Beantwortet: Wieviele Symbole darf mein Kelleralphabet beinhalten?

Mon, 21 Sep 2015 08:22:56 +0000

Hallo!

Wie viele Symbole und welche Symbole dein Kelleralphabet K beinhaltet, ist völlig egal (solange der Kellerautomat damit so funktioniert wie gefordert)! Nur das Kellerstartzeichen k0 ist in jedem Fall in K enthalten!

Das Kelleralphabet K ins insbesondere unabhängig vom Eingabealphabet E, dh. du kannst ganz andre Zeichen in K verweden als in E enthalten sind, du kannst nur einen Teil der Eingabezeichen auch im Keller verwenden oder du verwendest sowohl Zeichen als E als auch andere Zeichen in deinem Kelleralphabet.

Gruß, Janine (Tutorin)

Kommentiert: alternativer lösungsvorschlag: korrekt und deterministisch?

Mon, 21 Sep 2015 08:22:02 +0000

n den ersten beiden Zeilen hast du vergessen, die 0, bzw. die 1 auf den Keller zu legen. Die ersten beiden Zeilen müssen wie folgt aussehen:

(s0,1,k0) → (s1,1k0)

(s0,0,k0)→ (s2,0k0)

Max (Tutor)

Beantwortet: Beispiel für eine Auswahl bei nKA ohne Lambdaübergang?

Mon, 21 Sep 2015 08:20:18 +0000

Hallo,

genau so sieht ein Übergang aus, der einen Kellerautomat nichtdeterministische macht. Im dritten Foliensatz, Seite 14 ist nochmal ein nichtdeterminisischer Kellerautomat, ohne Lambdaübergang dargestellt.

Viele Grüße,

Sebastian (Tutor)

Beantwortet: leeres Wort und s0: Wie kann der Automat lambda lesen?

Mon, 21 Sep 2015 08:18:47 +0000

"Angenommen das Eingabeband ist leer (leeres Wort lambda). Der Startzustand ist s0."

Dann ist die Eingabe vollständig abgearbeitet und der Automat befindet sich in einem Endzustand -> Eingabe wird akzeptiert, ohne dass irgendwelche Zustandsübergänge nötig sind.

Gruß,

Tobias (Tutor)

Beantwortet: Wäre auch das leere Wort möglich?

Mon, 21 Sep 2015 08:14:52 +0000

Hallo,

das leere Wort liegt in der Sprache (Anzahl der Nullen = Anzahl der Einsen = 0) und wird bereits von dem Kellerautomaten akzeptiert, da der Anfangzustand s0 gleichzeitig ein Endzustand ist.

Noch eine Anmerkung: Der Übergang, den Sie vorschlagen ist nicht nur nicht erforderlich. Sie dürfen ihn bei der Aufgabe nicht verwenden, da der Automat dann nicht mehr deterministisch wäre.

Viele Grüße

Irina (Tutorin)

Beantwortet: Funktionsweise der Übergangsfunktionen?

Mon, 21 Sep 2015 08:12:50 +0000

Kurze Ergänzung hierzu:

In der Klammer steht immer das, was sich aus den neuen Eingabewort und dem obersten Kellersymbol ergibt:

zB:

(s0, 1, 1) => (s0, 11): neu gelesene 1 wird einfach auf den Keller geschrieben.

(s0, 1, 1) => (s0, 1): neu gelesene 1 wird NICHT in den Keller geschriebe, nur die alte bleibt drin.

(s0, 1, 1) => (s0, lambda): neu gelesene 1 löscht die 1 aus dem Keller.

Ich hoffe, dass es jetzt klarer wird.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König

Beantwortet: Warum wird k0 in der 2. Klammer nicht mehr hingeschrieben?

Mon, 21 Sep 2015 08:09:57 +0000

Man schreibt immer nur die letzten beiden Zeichen die sich an oberster Stelle des Kellers befinden auf. Also z.B. ... ->(s1,00) bedeutet, dass sich schon eine 0 (die hinterste 0) vor dem Übergang als oberstes Zeichen im Keller befinden muss und jetz noch eine 0 hinzukommt (die vordere 0).

Gruß

Johannes (Tutor)

Kommentiert: alternativer Lösungsvorschlag: auch deterministisch?

Mon, 21 Sep 2015 08:05:28 +0000

Der Automat in der Musterlösung ist detetministisch, weil er eben immer genau weiß, welchen Übergang er in Abhängigkeit von dem nächsten Symbol der Eingabe wählen muss. Hier gibt es keinen Lambda-Übergang, den er alternativ auswählen könnte.

Wenn du allerdings einen Lambda-Übergang dabei hast (bei der gleichen Kombination von Zustand und oberstem Zeichen im Keller!!!), kannst du dich entscheiden, ob du eben diesen Lambda-Übergang, oder einen der anderen Übergänge auswählst.

Viele Grüße

Lukas (Tutor)

Beantwortet: Gibt es eine Regel für Zustandsübergänge?

Mon, 21 Sep 2015 08:01:42 +0000

Hallo,

mit dieser Frage stehen Sie nicht alleine da, sie wird jedes Semester mehrfach gestellt, und wir beantworten Sie immer wieder gerne, weil die Antwort ganz einfach ist: Nein, es gibt keine allgemeine Regel :-) Sie müssen da letztendlich immer ein bisschen kreativ sein.

Aber so ganz stimmt das natürlich nicht, weil unsere Aufgaben immer nach ähnlichen Mustern ablaufen. Ich habe deshalb im letzten Semester ein paar Faustregeln aufgeschrieben, die Sie sich anschauen können: Link zum Post über Zustandsübergänge bei Kellerautomaten.

Trotzdem ist das Erstellen eines Kellerautomaten vor allem Übungssache, also rechnen Sie einfach Aufgaben, bis Sie es verstanden haben.

Viele Grüße und schöne Weihnachten

Lukas König

PS. Es wundert mich etwas, dass unser Forum zu den Poolaufgaben (s. obiger Link) bisher so wenig genutzt wird. Haben Sie etwa irgendwelche Probleme bei der Darstellung oder beim Einloggen? Sagen Sie uns bitte Bescheid, wenn das der Fall sein sollte!

Beantwortet: Vorgehensweise bei dieser Aufgabe?

Mon, 21 Sep 2015 07:59:13 +0000

Hallo,

ein genaues "Rezept" gibt es bei solchen Aufgaben nicht, vieles kommt erst mit der Zeit, wenn man viele Aufgaben gesehen hat. Eventuell kann eine Skizze des Kellers ganz hilfreich sein.

Die Herangehensweise in dieser Aufgabe ist so ähnlich wie in der VL (bzw. auf der Einführungsfolie im Tut), dort wurde ein KA konstruiert für Wörter der Form (a^n)(b^n). Dort hat man zuerst alle a's in den Keller geschrieben und anschließend für jedes b das man eingelesen hat, ein a aus dem Keller gestrichen. Wenn der Keller am Ende leer und das Wort zuende war, dann wusste man, dass das Wort genausoviele a's wie b's hatte.

Der einzige Unterschied in dieser Aufgabe ist, dass die 0er und 1er in beliebiger Reihenfolge auftauchen können. Das heißt, dass das, was man in den Keller reinschreibt, abhängt von dem Zeichen das man in s0 einliest.

Beim Definieren der Übergänge kannst du dir zuerst überlegen, ob lambda in der Sprache liegt (d.h. s0 = Endzustand = gleich viele 1er & 0er). Danach kannst du schrittweise parallel zu einer Skizze überlegen, wie du deine Übergänge definieren willst.

Bsp.: 0110. Wenn du eine 0 reinmalst, dann solltest du in s1 wechseln, da sonst das Wort 0 auch akzeptiert werden würde. Danach bietet es sich an, die 0 zu streichen wenn eine 1 folgt. Dann ist der Keller leer und im bisherigen Teilwort gab es genauso viele 0er wie 1er. Deswegen wechselst du zurück in s0 mit (s1,lambda,k0) -> (s0,k0). So kannst du dann weiter verfahren und auf eine Lösung kommen :)

Viele Grüße,

Vivian (Tutor)

Kommentiert: Fehlende Übergänge in Musterlösung?

Mon, 21 Sep 2015 07:57:16 +0000

Hallo,

du kannst die Übergänge in dem Kellerautomaten nicht definieren, denn sonst würdest du einen nicht deterministischen Kellerautomaten erzeugen und es wird explizit nach einem deterministischen Kellerautomaten gefragt.

Wegen:

(s1, lambda, k0) -> (s0, k0)

(s1,1,ko)->(s1,1k0) und (s1,0,ko)->(s1,0k0)

Grüße

Antonio (Tutor)