Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in AU-2-3

Beantwortet: optionales Übungsblatt 2, Aufgabe 8

Sat, 08 Jan 2022 08:49:37 +0000

Hallo uqyws,

1. Die Beschreibung der Überführungsfunktion ist so geregelt, wie auf den Folien, also etwas in den Keller schreiben und löschen eventuell noch nichts machen. Man braucht also nur die Idee, wie man die Grammatik dann mit diesen Regeln anwenden kann.

Zum Bsp 1: Die Grammatik lautet a^mb^na^nb^m, es gibt also gleich viel a's am Anfang wie b's am Ende und in der Mitte gleich viele b's wie a's. n und m können unabhängig von einander gewählt werden. Im Zustand s0 werden nur die a's gesammelt und gemerkt, bis der Mittelteil (b^na^n) abgearbeitet wurde. Sobald das erste b kommt sind wir im Zustand s1 und merken uns alle b's (und n>=1, also kommt auf jeden Fall ein b). In s2 müssen genau so viele a's kommen wie b's gerade eben (n Stück) und wenn dann alle a's abgearbeitet sind haben wir immer noch m Stück im Keller für die kommenden b's.

Also man braucht die Zustände wirklich aufgrund der Form der Grammatik.

Zu Bsp 2: Man muss nicht zwingend den Zustand wechseln, es geht auch ohne. Zur Strukturierung kann es helfen, in s1 geht man, wenn das Wort nichtleer ist.

2. Du kannst (s4; λ; k0) schreiben, ist auf jeden Fall kein Fehler. Es ist Konvention, dass man das am Ende auch weglassen kann, wenn das Wort abgearbeitet ist und man im Endzustand ist, schaden tut es dennoch nicht.

3. Ein Verfahren gibt es so direkt nicht, man sollte die Grammatik noch einmal anschauen und auch Sonderfälle beachten. Dann kann man seinen Automaten Schritt für Schritt durchgehen, ob die alle berücksichtigt werden. Aber einen garantierten Weg gibt es leider nicht.

Ich hoffe, ich konnte dir weiterhelfen, viel Erfolg noch beim Lernen und viele Grüße

Anne (Tutorin)

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)

Beantwortet: Übung 2 Nr 5 - Lösung

Mon, 18 Dec 2017 13:13:03 +0000

Hallo,

Du meinst vermutlich folgendes in der Ableitung des Testworts:

(s1, 001110, k0) |- (s0, 001110, k0)

Dies geschieht aufgrund des letzten Übergangs (s1, λ, k0) → (s0, k0) in δ. Das λ bedeutet hier (auf der linken Seite), dass nichts eingelesen wird.

Eine Erklärung zu deiner Frage gibt es bereits hier im Forum, siehe: http://info2.aifb.kit.edu/qa/index.php?qa=4729&qa_1=konfigurationsfolge-lambda-%C3%BCbergang

Bitte poste deine zukünftigen Fragen zu Aufgaben aus Übungen, Tutorien oder Altklausuren in der jeweiligen Kategorie (siehe rechts). So kann deine Frage besser zugeordnet werden und du siehst, ob es eventuell schon eine Antwort gibt.

Viele Grüße

Laura (Tutor)

Beantwortet: Konfigurationsfolge lambda-Übergang

Thu, 05 Jan 2017 11:55:49 +0000

lambda-Übergänge sind bei Kellerautomaten erlaubt, d.h. der Kellerautomat kann auf seinem Keller "arbeiten", ohne dass sich der Lesekopf weiterbewegt.

Man kann sich zwischen den Eingabesymbolen des Wortes beliebig viele lambdas (leere Wörter) vorstellen.

Bei dem Konfigurationsübergang (s1,001110,k0) -> (s0,001110,k0) wird folgende Überführungsfunktion verwendet: (s1,λ,k0) →(s0,k0), d.h. die erste 0 des Restwortes wird noch gar nicht verarbeitet.

Da die Überführungsfunktion (s1,0,k0) →... nicht definiert ist, ist der Kellerautomat sogar deterministisch.

Viele Grüße Philipp (Tutor)

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: Hat s0 einen Sonderstatus?

Mon, 21 Sep 2015 08:24:31 +0000

Hey,

das hängt damit zusammen welcher Zustand der Endzustand ist! Da hier s0 der Endzustand ist kannst du nach der ersten Eingabe (nach der ja dein Wort nicht mehr zulässig ist) nicht in einem Endzustand sein. Deshalb musst du wechseln.

Grüße,

Elisabeth (Tutor)

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)

Beantwortet: alternativer lösungsvorschlag: korrekt und deterministisch?

Mon, 21 Sep 2015 08:21:38 +0000

Hallo,

ich gehe davon aus, dass du bei den ersten beiden Zuständen die 1, bzw, die 0 vergessen hast. Wenn du das noch machst, müsste der so auch richtig sein.

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: Unterschied Deterministischen und Nichtdeterministischen Kellerautomaten?

Mon, 21 Sep 2015 08:16:23 +0000

Ein nichtdet. KA zeichnet sich dadurch aus, dass er bei einem Eingabesymbol die "Auswahl" zwischen mehreren Übergangsregeln hat. Dabei betrachtet man nur den Linken Tupel der Übergangsregel (also Links vom Pfeil).

Am Beispiel (unabhängig der Aufgabe):

(s0,1,1) -> (Beliebiger_zustand, Beispielzeichen)

(s0,lambda,1) -> (Beliebiger_zustand, Beispielzeichen)

Sei nun o.B.d.A. das oberste Zeichen im Keller eine 1 und der KA grade im Zustand s0:

Wenn das folgende Eingasymbol eine 1 ist kann der Automat nun die 1. Übergangsregel verwenden oder aber er ignoriert das Eingasymbol und verwendet den Lamdaübergang (also 2. Übergangsregel) und geht in die entsprechend auf der rechten Seite definierten Zustände.

Da der KA hier die Wahl hat und nicht klar ist, welche Übergangsregel er verwenden muss würde es sich hier um einen nichtdet. KA handeln.

Wichtig ist, hier Lambda richtig zu verstehen. Das heißt NICHT, das es kein Eingabesymbol mehr gibt oder die Eingabe leer ist, sondern dass der Automat die Eingabe schlicht ignoriert. Sprich, der Übergang ist in dem Falle nur noch vom aktuellen Zustand und obersterstem Kellersymbol abhängig, und nicht auch noch vom Eingabesymbol.

Philippe (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)

Beantwortet: alternativer Lösungsvorschlag: auch deterministisch?

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

Hallo,

nein, der Automat ist nichtdeterministisch, da neben diesen Übergängen noch ein Lambda-Übergang von s0, k0 existiert. Man kann sich das so vorstellen, dass der Automat nicht "weiß" , ob er direkt weitermacht (lambda), oder auf die Eingabe von 0 oder 1 wartet.

Viele Grüße

Philippe (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)

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

Mon, 21 Sep 2015 07:56:02 +0000

Hallo,

wo genau kommen denn Ihrer Meinung nach diese Übergänge vor? Ich habe mir die Lösung nochmal angeschaut uns es gibt nur drei Übergänge, bei denen in s1 im Keller ein k0 steht. Das sind folgende Übergänge:

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

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

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

Bei allen drei Übergängen wird bei der Ableitung der lambda-Übergang verwendet, der auch definiert wurde:

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

Hat Sie vielleicht das verwirrt?

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König