Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in KEL-AA

Beantwortet: Beispiel zu ndet. KA

Thu, 03 Feb 2022 13:49:08 +0000

Hallo ueyfv,

dein vorgeschlagener Automat ist in der Tat nichtdeterministisch, da ein Lambda-Übergang im Startzustand möglich ist. Zu Beginn kann der Automat also theroretisch entweder in s0 bleiben oder in se wechseln.

Bei der Frage, ob der nichtdeterministische Kellerautomat das Wort aabb erkennt, musst Du Dir alle möglichen Übergänge anschauen. Falls eine Folge von Zustandsübergängen existiert, nach der der Kellerautomat nach Abarbeitung des Wortes im Endzustand landet, so ist er auch in der Lage, das Wort zu erkennen. Unabhängig davon, ob er am Anfang auch einen anderen Übergang wählen kann oder nicht.

Viele Grüße

Jannik (Tutor)

Beantwortet: Unterscheidung von deterministischen und nichtdeterministischen Kellerautomaten

Wed, 02 Feb 2022 16:19:08 +0000

Hallo uwlxy,

wenn es zwei mögliche Zustandsübergänge im selben Zustand und mit demselben Kellerinhalt gibt, entspricht das genau der Definition eines nichtdeterministischen Kellerautomaten. Bei deterministischen Automaten ist dies nicht erlaubt, es muss abhängig vom aktuellen Zustand und Kellerinhalt eindeutig sein, welcher Zustandsübergang als nächstes erfolgt.

Viele Grüße

Jannik (Tutor)

Beantwortet: Aufgabenstellung HK 2019 Aufgabe 1

Sat, 20 Mar 2021 15:52:49 +0000

Hey, du hast L schon richtig verstanden. Jetzt wird aber die Sprache L(A)=L* (der Stern ist hier das Relevante) betrachtet, also kannst du die einzelnen Worte aus L mehrfach hintereinander ausführen. Daher sind auch solche Wörter wie abaaabcc in L(A) enthalten. Wichtig ist, dass die einzelnen Wörter aus L sind, in diesem Fall ab und aaabcc (hier gilt auch, wie du richtig gesagt hast, erst a, dann b und am Schluss c). Ich hoffe, das hilft dir weiter

Beantwortet: nicht deterministischer Kellerautomat

Fri, 19 Mar 2021 15:38:15 +0000

Hallo uzfnw,

ein Kellerautomat muss nur dann deterministisch sein, wenn es in der Aufgabenstellung so gefordert ist. Dass das in der Praxis sicherlich etwas anderes ist, ist klar - aber für die Klausur ist das der wichtige Punkt, auf den du achten musst.

Ob deine Variante mit den Lambda-Übergangen so immer funktioniert und sinnvoll ist, sei mal dahingestellt.

Beste Grüße,

Martin (Tutor)

Beantwortet: HK 2019 Aufgabe 1

Fri, 19 Mar 2021 11:15:00 +0000

Ein deterministischer Automat ist ein Spezialfall eines nichtdeterministischen Automaten ist. Also kann man da auch einen deterministischen Automaten auftsellen.

Beantwortet: was ist der unterschied zwischen dem Wort und der Bandinschrift

Mon, 10 Feb 2020 15:18:38 +0000

Hallo uivit,

beziehst du dich bei deiner Frage auf den Kellerautomaten? So ist deine Frage nämlich gelabelt. Kellerautomaten haben allerdings keine Bandinschrift, sondern nur ein Eingabealphabet. Das Eingabealphabet ist der Zeichenvorrat, aus dem das Wort besteht, das dein Schreib-/Lesekopf liest.

Den Begriff Bandinschrift hast du sicher von den Turingmaschinen. Bandinschrift ist so definiert: "Die Bandinschrift ist der Inhalt des Bandes beginnend mit dem linkesten "Nichtleer"-Feld rechts neben einem Leerfeld (*) und endend mit dem Zeichen im rechtesten Nichtleer-Feld links neben einem Leerfeld, sofern sich das Leerfeld rechts vom S/L-Kopf befindet. Andernfalls endet die Bandinschrift mit dem Zeichen an der Position des S/L-Kopfes."

Wenn deine TM entscheiden soll, ob ein Wort Teil der Sprache ist, dann wird tatsächlich dein Wort als Bandinschrift verwendet. Jetzt ist für jeden Zustand und jedes Zeichen des Wortes festgelegt, was die TM tun soll. Hält sie am Ende in einem Endzustand, ist das Wort erkannt, andernfalls nicht. Hier ist das Wort die initiale Bandinschrift. Die Bandinschrift kann allerdings im Laufe des Algorithmus verändert werden.

Ich hoffe, das beantwortet deine Frage.

Viele Grüße
Hannah (Tutorin)

Beantwortet: Kellerautomaten alternative Lösung

Thu, 06 Feb 2020 09:30:08 +0000

Es gibt auf jeden Fall mehrere Lösungen.

Zur Überprüfung sollte dein KA die gegebenen Wörter der Sprache akzeptieren und keine anderen. (Überprüf dies mit eigenen Worten)

LG, Nico (Tutor) (Alle Angaben ohne Gewähr)

Beantwortet: HK, WS 18/19, Aufgabe 1

Tue, 14 Jan 2020 08:48:51 +0000

Hallo,

zu 1):
Nur die Sprache L beinhaltet das leere Wort nicht. Der Kellerautomat selbst soll jedoch die Sprache L(A) = L* erkennen, also ein beliebig vielfaches der Spache L. Somit ist insbesondere auch das leere Wort Teil der Sprache und muss vom Kellerautomaten akzeptiert werden.

zu 2):
Hier hast du Recht, b und c sind in diesem Fall für das Kelleralphabet überflüssig, machen es dennoch auch nicht falsch, man kann auch Zeichen, die nicht verwendet werden im Kelleralphabet definieren.

Viele Grüße

Moritz (Tutor)

Beantwortet: zusätzliche Regeln erforderlich?

Mon, 06 Jan 2020 14:44:47 +0000

Hallo,

Zur ersten Frage: So, wie es in der Musterlösung angegeben ist, funktioniert der Kellerautomat in jedem Fall. Mit dem betrachteten Übergang von (s3, 1, b) --> (s3,b1) wird der "Übertrag" also die gemerkte 0 dann bereits früher abgearbeitet, indem das b gelöscht wird. Hier lohnt es sich Aufgabenteil b) genauer zu betrachten. Ich denke, deine Lösung würde dennoch auch funktionieren.

Zur zweiten Frage, hier die entsprechende Ableitung des Testworts 100.

(s0, 100, k0) ⊢ (s3, 00, 1k0) ⊢ (s3, 0, bk0) ⊢ (s3, λ, k0) ⊢ (s0, k0)

Dabei ist zu beachten, dass die 1, die in den Keller geschrieben wird in Zustand s3 beim Lesen der 0 bereits durch das b überschrieben wird und somit nicht mehr im Keller steht. Daher muss sie nicht mehr gelöscht werden.

Viele Grüße,

Dominik (Tutor)

Beantwortet: Kap.3 Kellerautomaten, Folie 15

Wed, 09 Jan 2019 11:04:14 +0000

Hallo uxiwq,

die Beziehung ist so wie sie auf der Folie steht richtig:

„->“:

Der deterministische endliche Automat (genau ein Folgezustand pro Konfiguration) ist ein Spezialfall eines nichtdeterministischen endlichen Automaten (endliche Menge an Folgezuständen pro Konfiguration).

„<-“:

Da du jeden nichtdeterministischen endlichen Automaten in einen Deterministischen umwandeln kannst (Algorithmus aus Tut 2), ist die Sprachmächtigkeit von beiden Automatenformen entsprechend gleich.

Ich hoffe ich konnte Dir damit helfen!

Viele Grüße

Claus (Tutor)

Beantwortet: Voraussetzungen für die Terminierung des Kellerautomaten

Sat, 10 Feb 2018 07:13:40 +0000

Hallo,

der Keller muss nicht leer sein, der Automat muss sich lediglich in einem Endzustand befinden.

Viele Grüße

Niklas (Tutor)

Beantwortet: prüfen ob eine Überführungsfunktion richtig ist

Sat, 06 Jan 2018 15:53:52 +0000

Ich bin nicht sicher, ob ich ganz richtig verstehe, was Sie wissen möchten.

Sie haben recht, ein Testwort zeigt nur für den einen Fall, dass die Überführungsfunktion in diesem Fall korrekt ist; es kann keine Aussage über ihre Korrektheit im Allgemeinen abgeleitet werden (außer, wenn sie nicht korrekt ist - dann reicht u.U. ein einziger Testfall).

Durch Testen kann man nie vollständig sicher sein, dass die Überführungsfunktion korrekt ist.

Leider gibt es allerdings für alle Automatentypen ab det. Kellerautomaten kein automatisches Beweisverfahren, um zu zeigen, dass die Semantik der Überführungsfunktion korrekt ist (die Semantik ist "das, was das Programm tut"). Sie kennen das ja vom Programmieren in Java etc. Wenn man sicher sein will, dass ein Programm korrekt ist, muss man sich schon hinsetzen und das in jedem Einzelfall von Hand beweisen.

(Es gibt Model-Checking-Verfahren, die einen halbautomatischen Mittelweg darstellen, aber damit haben wir uns nicht beschäftigt.)

Kurz gesagt, können Sie also leider nicht mit dem XWizard überprüfen, ob eine Überführungsfunktion korrekt ist. Und auch sonst gibt es kein automatisches Werkzeug, das das kann. Für die Klausur müssen Sie trotzdem in der Lage sein, korrekte Überführungsfunktionen anzugeben - und diese Korrektheit eventuell beispielhaft an einem Testwort zu demonstrieren.

(Beweisen, dass eine Überführungsfunktion korrekt ist, müssen Sie dagegen normalerweise nicht.)

Beantwortet: zusätzliches Symbol für das Kelleralphabet

Fri, 05 Jan 2018 14:10:03 +0000

Hallo,

ein kurzer Blick in das neue Lehrbuch sollte deine Frage beantworten können.

Auf S.49 findest du die Definition eines det. Kellerautomaten mit u.a. folgendem Inhalt:

E ist das Eingabealphabet, das alle Zeichen enthält, aus denen die Eingabe (ohne k0 ) bestehen kann.
K ist das Kelleralphabet, das dem Bandalphabet bei Turingmaschinen entspricht. Dazu gehört insbesondere das k0 -Zeichen zur Kennzeichnung des Kellerbodens (aber nicht unbedingt die Zeichen aus E), und es können noch beliebige weitere Zeichen darin enthalten sein.

Eine pauschale Antwort auf deine Frage wann man wie vorgeht gibt es nicht.

In der Aufgabe wird das b dafür verwendet um anzuzeigen, dass noch eine weitere 0 gelesen werden muss, um eine bereits gelesene 1 auszugleichen (auszugleichen im Sinne der formalem Sprachdefinition, dass Wörter der Sprache doppelt so viele Nullen enthalten als Einsen).

Ich hoffe ich konnte dir weiterhelfen.

LG Tutor

Beantwortet: mehrere Kellerzeichen gleichzeitig löschen?

Fri, 05 Jan 2018 13:57:03 +0000

Hallo,

Schauen wir uns hierfür ein Teil der Definition aus dem Lehrbuch an (S.49-50):

"Wenn sich der Kellerautomat in Zustand s ∈ S beﬁndet und auf dem Eingabeband e gelesen wird und das oberste Kellerzeichen k ∈ K ist, dann wird k im Keller durch das ganze Wort v ∈ K* ersetzt, indem dieses von hinten nach vorne zeichenweise auf den Keller gepusht wird".

Desweiteren gilt für die Zustandsüberführungsfunktion folgendes:

δ∶ S × (E ∪ {λ}) × K → S × K*

Da der Lese/Schreibe-Kopf des Kellers immer auf dem obersten Kellerzeichen steht und nur dieses liest, sind nur Zustandsübergänge folgender Form erlaubt:

δ(s, e, k) = (s ′ , v) mit s, s' ∈ S, e ∈ E, k ∈ K und v ∈ K*.

k besitzt daher nur ein Element aus K (und nicht wie du es angeben wolltest zwei Elemente (00).

Zusammenfassend können wir also sagen, dass pro Rechenschritt jeweils nur das oberste Zeichen des Kellers überschrieben bzw. gelöscht werden kann.

Ich hoffe ihr konnte dir damit weiterhelfe.

LG Tutor

Beantwortet: Kellerautomaten auf Richtigkeit überprüfen

Sun, 23 Jul 2017 17:32:21 +0000

Hallo,

grundsätzlich gibt es für Kellerautomaten ja viele richtige Lösungen und wenn sich bei deinen eigenen Automaten die Testwörter ableiten lassen, ist das schon einmal ein guter Hinweis auf ihre Richtigkeit. Allerdings reicht das Erkennen der Wörter einer Sprache nicht aus, es dürfen anders herum die Wörter, die nicht zur Sprache gehören, auch nicht vom Automaten akzeptiert werden.
Am besten ist es immer sich zu überlegen, wenn er das Testworter erkennt, ob es wirklich nur die Möglichkeit gibt zugehörige Wörter der Sprache zu akzeptieren, oder ob es auch ein Gegenbeispiel gibt.

Liebe Grüße und viel Erfolg beim Lernen!

Beantwortet: KA |w|a mod 2 = 0

Sun, 12 Feb 2017 06:18:56 +0000

Hallo,

ja das ist durchaus möglich. Es ändert sich ja nichts am Prinzip eines Kellerautomatens, wenn du beim Einlesen des gleichen Zeichens löschst oder wenn das Löschen durch ein neues Zeichen initiiert wird.

Liebe Grüße

Beantwortet: Aufgabe 44 Übungsbuch

Tue, 07 Feb 2017 15:50:20 +0000

Hallo,

wenn du s3 und s4 zusammenfasst, nimmst du an, dass in diesem Zustand für die Eingabe "a" oder "b" immer gelöscht wird. Das würde aber auch bedeuten, dass nach der Eingabe bzw. dem Herauslöschen durch die hinteren "a"s weitere "b"s folgen dürften, da du den Zustand nicht wechselst. "aaaccbab" wäre dann akzeptiert. Die Sprache definiert aber strikt, dass hinten bnap gilt. Du darfst die Zustände also nicht zusammenfassen.

Beantwortet: Zustände bei Kellerautomaten

Tue, 07 Feb 2017 10:27:31 +0000

Hallo,

es ist schwierig eine generelle Regel anzugeben, aber es ist überhaupt nicht relevant genau die Musterlösung zu haben. Solange dein Automat das macht was gefordert ist bekommst die die volle Punktzahl, auch wenn du 20 Zustände dafür brauchst.

Wenn du noch eine genauere Antwort möchtest, gib doch mal ein Beispiel an, das man dann gemeinsam durchsprechen kann.

Christian (Tutor)

Aufwand Spracherkennung

Wed, 25 Jan 2017 06:17:25 +0000

Hallo

In der nuKIT Umfrage zu Kapitel 3 ist bei der siebten Frage als richtig vermerkt :
1. Der Aufwand zur Spracherkennung bei deterministischen Kellerautomaten ist linear in der Wortlänge.
Weiter ist auch richtig :
2. Der Aufwand zur Spracherkennung bei deterministischen Kellerautomaten ist $O(n^3)$.

Wie können diese Antworten denn zusammenpassen?

Beantwortet: Musterlösung, $(s_2, 1100000, k_0) \Rightarrow (s_3, 1100000, bk_0)$, wie kommt dieser Übergang zustande?

Mon, 23 Jan 2017 16:38:29 +0000

Hat sich glaube ich erledigt, habe nocheinmal die Vorlesungsfolien durchstöbert.

"falls δ(s,λ, k) definiert, ignoriert KA für (Zustand=s, Kellerzeichen=k) das Eingabeband und verändert nur Keller und Zustand."

Das bedeutet ja dass ich, solange die Übergänge vorher definiert habe, jederzeit einen λ- Übergang einbauen darf oder?

Beantwortet: alternativlösung

Sun, 15 Jan 2017 14:38:32 +0000

Hallo,

Um welche Aufgabe handelt es sich hier genau? In der Aufgabe KEL-AA geht es um ein Wort mit 1 und 0 und nicht a und b.
Falls du hier nur a/b mit 1/0 vertauscht hast, ist die Lösung von dir dennoch nicht korrekt (Ich rede jetzt von 1=b und 0=a), da hier immer genau zwei 0 direkt hintereinander eingegeben werden müssen, damit überhaupt eine 1 eingelesen werden kann.
Laut der Definition der Sprache kommt es aber nur auf die Anzahl, und nicht die Reihenfolge an, demnach wäre auch 010 korrekt, was in deinem Fall nicht akzeptiert werden würde.

Grüße, Sören (Tutor)

Beantwortet: (s3; 1; b) -> (s3; b1) Kann man Kellerzeichen im Keller tauschen?

Sat, 14 Jan 2017 13:15:36 +0000

Man kann nur das oberste Kellerzeichen lesen und dann durch ein beliebiges Wort $\in K^*$ ersetzen.

Bei $(s_3,1,b) \rightarrow (s_3,b1)$ werden nicht die obersten zwei Kellerzeichen getauscht, sondern nur das oberste Kellerzeichen $b$ durch $b1$ ersetzt. Diese Überführung ist also erlaubt und somit ist auch die Ableitung des Testwortes korrekt.

Viele Grüße

Philipp (Tutor)

Beantwortet: Kellerautomat Zustandsüberführungsfunktion

Tue, 15 Nov 2016 17:02:26 +0000

Die Zeichenkette $v$ bezeichnet die Zeichen, die oben auf den Keller abgelegt werden. Das ist oft das leere Wort $\lambda$ oder eine Kette aus zwei Zeichen. Im ersten Fall wird das oberste Zeichen aus dem Keller entfernt und danach $\lambda$ hineingeschrieben, effektiv wird also das oberste Zeichen gelöscht.

Der zweite Fall ist, dass das oberste Zeichen gelöscht wird und stattdessen zwei Zeichen hineingeschrieben werden, der Keller wächst also um ein Zeichen an. Oft ist dabei das untere der beiden hineingeschriebenen Zeichen dasselbe, das zuvor schon im Keller stand, sodass effektiv nach dem Rechenschritt ein Zeichen auf den Keller oben abgelegt wurde.

Eher selten (im Kontext der Vorlesung), aber genauso möglich sind Fälle, wo ein Zeichen in den Keller geschrieben wird, das bedeutet, dass das oberste Zeichen also einfach nur ersetzt wird, sowie Fälle, wo mehr als zwei Zeichen in den Keller geschrieben werden. Um die Sprachmächtigkeit des Kellerautomaten zu erhalten, ist es wichtig, dass beliebig lange Zeichenketten für $v$ zugelassen werden. Einen Anwendungsfall dafür sehen Sie etwa im Buch auf Seite 179 (oder auf den Folien ab 3-24), wo ein Algorithmus zur Konstruktion eines Kellerautomaten zu einer beliebigen Kontextfreien Grammatik präsentiert wird.

Beantwortet: Darf man EA statt KA angeben, obwohl Aufgabe nach KA verlangt?

Fri, 12 Feb 2016 22:29:48 +0000

Hallo ucczn!

Nein, wenn in der Aufgabe explizit nach einem Kellerautomaten gefragt ist, dann musst du auch einen Kellerautomat angeben!

Die Lösung ist hier dann aber ganz einfach: Du benutzt den Keller einfach nicht ;)

Im Grunde genommen überlegst du dir also die Zustandsübergänge wie bei einem endlichen Automaten, schreibst sie dann aber formal wie der Übergänge eines Kellerautomaten auf und dein Kellerinhalt bleibt bei jedem Übergang einfach unverändert "k0".

Ich hoffe, das hilft dir weiter!

Viele Grüße,
Janine (Tutorin)

Beantwortet: A.45 a) Verständnisfrage lambda

Fri, 05 Feb 2016 15:11:57 +0000

Hallo,

ja das Wort 010 kann gelesen werden:

(s0, 0, k0) → (s1, 0k0)
(s1, 1, 0) → (s2, λ)
(s2, λ, k0) → (s3, bk0)
(s3, 0, b) → (s3, λ)
(s3, λ, k0) → (s0, k0).

Viele Grüße,

Marc (Tutor)

Beantwortet: Alternativlösung

Fri, 13 Feb 2015 09:55:12 +0000

Hey,

Eingaben ignorieren ist zulässig (genau so wie du es ausgeführt hast).

Probier mal das Testwort "001", soweit ich das sehe kann es nicht ausgeführt werden.

Beantwortet: Wann ist ein Kellerautomat nicht deterministisch?

Thu, 13 Nov 2014 08:34:24 +0000

Hallo,

ein Kellerautomat ist dann nichtdeterministisch, wenn wir mehr als eine Möglichkeit haben, ein Zustandsübergang zu machen. Das ist dann der Fall, wenn:

wir für denselben Zustand, Eingabe und Kellerzeichen zwei Optionen für die Zustandsüberführung haben, also zum Beispiel
- (s1,a,a) -> (s2,aa)
- (s1,a,a) -> (s3,lambda)
wir die Möglichkeit haben sowohl ein Eingabezeichen abzuarbeiten als auch einen Lambda Übergang (also kein Eingabezeichen abarbeiten) zu machen

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

Hinzuzufügen ist, dass jeder deterministische Kellerautomat auch automatisch nichtdeterministisch ist.

Grüße

Simon

Beantwortet: Wann genau akzeptiert ein KA ein Wort?

Thu, 13 Nov 2014 08:33:22 +0000

Der Keller muss nicht leer sein. Das Wort muss vollständig abgearbeitet sein und der Kellerautomat muss in einem Endzustand sein. Allerdings sind nach dem Einlesen des letzten Zeichens noch lambda-Übergänge möglich, was in verschiedenen Aufgaben ausgenutzt wird, um in einen Endzustand zu wechseln.

Tobias (Tutor)

Beantwortet: Ansatz mit Kelleralphabet von 0 und 1

Thu, 13 Nov 2014 08:30:05 +0000

In deiner Lösung gibt es Übergänge nach s5, aber dieser Zustand ist weder in S noch gibt es irgendwelche Übergänge aus diesem Zusand heraus. Da dieser Zustand aber in der Ableitung des Testwortes vorkommt, nehme ich an, dass du vergessen hast, etwas hinzuschreiben.

Tobias (Tutor)

Beantwortet: Alternativer Ansatz

Thu, 13 Nov 2014 08:19:51 +0000

Hallo,

also deine Ansätze sind schon ganz gut. Inhaltlich scheitert es leider daran, wenn das Wort anfangs mehr Nullen als Einsen hat und im hinteren Teil des Wortes sich das dann umdreht.

Beispiel: 001100

Hier sollte es möglich sein nochmal in s0 zu starten, sobald der erste Teil abgearbeitet ist. Versuch mal etwas in die Richtung.

Zu den kommentierten Übergängen:

Leider ist es nicht definiert, obere Kellerzeichen umzubenennen oder ähnliches. Du darfst also nur löschen, hinzufügen oder stehenlassen.

Gruß,

Adam (Tutor)

Beantwortet: Wieso "a" notwendig?

Thu, 13 Nov 2014 08:18:49 +0000

Hallo,

du hast natürlich recht, man braucht das a nicht. Allerdings kann man so viele Zeichen wie man möchte in sein Kelleralphabet schreiben. Das heißt ja lediglich, dass der Automat sie in den Keller schreiben könnte, nicht aber, dass er sie verwenden muss.

Viele Grüße

Philippe (Tutor)

Beantwortet: Alternativer Lösungsvorschlag

Thu, 13 Nov 2014 08:17:41 +0000

Hallo,

dass Sie zwei Zeichen bei einem Übergang in den Keller schreiben bei (s1,1,1) -> (s1,111) , ist zwar, laut Definition im Skript, nicht ausgeschlossen, aber sehr unüblich.
Bei folgendem Übergang (s1,1ko) -> (s1,11ko) sollten Sie das k0 streichen. Der Automat kennt immer nur das oberste Kellerzeichen.

Viele Grüße
Friederike Pfeiffer

Beantwortet: Kellerzeichen anstatt löschen gleich überschreiben?

Thu, 13 Nov 2014 08:15:08 +0000

ja, das darfst du ohne weiteres.

Beste Grüße

Fabian (Tutor)

Beantwortet: Weiterer alternativer Lösungsvorschlag

Thu, 13 Nov 2014 08:09:17 +0000

Hallo,

du darfst für einen deterministischen Kellerautomaten nur dann einen Lambda-Übergang definieren, wenn du sonst keinen Übergang für die entsprechende Zustands/Kellerzeichen-Kombination definiert hast. Ansonsten ist der Kellerautomat nicht mehr deterministisch, da bei dir z.B. nicht klar ist, was im Zustand s0 mit oberstem Kellerzeichen k0 als Übergang gewählt werden soll.

Selbst wenn man deinen Automaten als nicht-deterministisch ansieht, ist kein Übergang für (s0, 1, 1) oder (s0, 0, 0) definiert, d.h. dein Automat erkennt keine Wörter mit zwei aufeinander folgenden 0en oder 1en.

Beste Grüße

Fabian (Tutor)

Beantwortet: Frage zum leeren Wort und Alternativlösung

Thu, 13 Nov 2014 08:01:33 +0000

Hallo,
Zur ersten Frage: s0 ist ja Endzustand, warum sollten Sie also noch einen lambda-Übergang nach s0 benötigen? Sie sind ja bereits in s0, wenn Sie das leere Wort haben.
Zur zweiten Frage:
(s0,1,k0) -> (se,bk0): das würde bedeuten, dass Ihr KA auch nur 1 erkennt.
Durch (s0,0,k0) -> (s0,0k0) und (s0,0,1) -> (s0,lambda) erkennt ihr Automat auch 01. Auch mit dem Übergang (s0,1,1) -> (s0,b1)könnten Sie Probleme bekommen, da Sie sozusagen hinter einer ganzen Null (b) noch eine halbe Null (1) gespeichert haben. Das bekommen Sie so nicht bei allen Wörter wieder raus, z.B. bei 000110. Das ist glaube ich das Hauptproblem be Ihrem Automaten.

Viele Grüße
Friederike Pfeiffer

Beantwortet: Wofür steht das "b"?

Thu, 13 Nov 2014 08:00:18 +0000

Hallo,

"b" ist ein Element des Kelleralphabets K={0,1,a,b,k0}. Es ist ein "Hilfselement" ohne dem die Umsetzung des Kellerautomaten nicht möglich wäre. In der Aufgabe soll ein Kellerautomat für eine Sprache angegeben werden, bei der jedes Wort doppelt so viele 0 wie 1 enthält. Das heißt, wenn auf dem Eingabeband eine 0 auf eine 1 folgt, kann die 1 gelöscht werden, aber wir brauchen das "Hilfs-b" um uns zu "merken", dass noch eine 0 kommen muss. Folgt diese zweite 0, dann wird das b gelöscht.

Ich hoffe du verstehst, was ich meine.

Grüße

Theresa (Tutor)

Beantwortet: Wieso Endzustand gleich dem Anfangszustand?

Thu, 13 Nov 2014 07:57:33 +0000

Warum denn nicht? Das leere Wort ist zulässig und Element der Sprache.

2*0=1*0.

Viele Grüße,

Jacob (Tutor)

Beantwortet: Geänderte Musterlösung

Thu, 13 Nov 2014 07:53:12 +0000

Sie haben recht, dass die Einträge in diesem Thread bezogen auf die Aufgabe etwas verwirrend sind. Das liegt daran, dass wir die Musterlösung im Vergleich zum letzten Jahr abgewandelt und verändert haben. Demnach haben hier nicht mehr alle Einträge zu der Aufgabe gepasst. Diese habe ich nun zusätzlich zensiert, so dass Sie nicht verwirrt sind.

Und die Antwort auf Ihre Frage lautet, dass der Automat so wie in der Musterlösung beschrieben deterministisch sind. Erklärungen dazu finden Sie in den entsprechenden Fragen zu dieser Aufgabe.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König

Beantwortet: Deterministisch oder nichtdeterministisch?

Thu, 13 Nov 2014 07:51:27 +0000

Hallo,

(s0,a,k0)-->...
(s0,b,k0)-->...
deterministisch

(s,a,b) -> ...
(s,lambda, k0) -> ...
deterministisch

(s,a,b) -> ...
(s,lambda, k0) -> ...
(s,a,k0) -> ...
nicht deterministisch

Viele Grüße
Friederike Pfeiffer

Beantwortet: Frage zum Nichtdeterminismus

Thu, 13 Nov 2014 07:49:43 +0000

Bei einem Lambda-Übergang ist Ihr Automat nicht-deterministisch, sobald Sie zwei Übergäng vom gleichen Zustand aus mit dem gleichen Kellerzeichen haben, also z.b.:

(s0,a,k0) -> ...
(s0,lambda,k0) -> ...
wäre nicht-deterministisch.

(s0,a,a) ->...
(s0,lambda,k0)->...
wäre deterministisch.

Prinzipiell ist es aber ganz einfach zu erkennen: Gibt es irgendwann die Möglichkeit, zu "wählen", welchen Zustandsübergang ich verwende. Wenn das der Fall ist, dann ist der Automat nicht-deterministisch.

Viele Grüße
Friederike Pfeiffer

Beantwortet: Auch mit deterministischem KA lösbar?

Thu, 13 Nov 2014 07:47:20 +0000

Am zweiten Teil deines Ansatzes muss man glaube ich noch arbeiten. So realisierst du nicht, dass zwei einsen folgen müssen, nachdem eine 0 eingelesen wurde, wenn man nur ko im Keller hat. Ist aber ohne konkrete Übergänge schwer zu sagen.

Beachte aber, dass dein KA durch den lambda-Übergang nicht deterministisch wird.

Ja, man kann auch mehrere Zeichen auf einmal in den Keller schreiben. Nachdem sie in den Keller eingetragen wurden, wird der Lese-/Schreibkopf für den Keller auf das oberste Kellerzeichen gesetzt. Das heißt nach dem Eintragen mehrerer Zeichen auf einmal weiß der KA nicht mehr, dass er dies einmal getan hat. Es wird dann immer nur das oberste Kellerzeichen betrachtet.

Viele Grüße,

Sven (Tutor)