Fachrat Informatik - Forum

Die Zustandsanzahl kann von Lösung zu Lösung variieren, je nachdem wie viele epsilon Übergänge Du hast bzw. ob Dein Automat dertministisch ist.

Wenn es Sinn macht, könnte man hier eine Lösung diskutieren...
Ich könnte ja meine Posten...wenn es denn gewollt ist.

Ich würd gern ne Lösung sehen...und gebe dir hiermit freie Hand

Glück auf!

Sind auf jedenfall 2 Zustände nur, von denen der EINE als Startzustand (aber bei weitem nicht nur) fungiert, der ANDERE als Zustand, um "2 Nullen zu garantieren", also erreicht man den durch die Eingabe einer Null, und kann ihn nur durch eine Null verlassen.
Zudem müssen überall noch passend die anderen Übergänge definiert werden, insgesamt sind das 13, pro zustand 6 (0,1 Eingabe x 0,1,Kellersymbol IM KELLER = 2x3 = 6 x 2 Zustände = 12) plus den epsilonübergang in den endzustand (13)...aus dem startzustand

schönen dank Eike
hoffe habs wenigstens richtig verstanden...aber das geht scho

Also! Ich glaube, dass das nicht so ganz stimmt. Du hast schon Recht, dass man einen Zustand braucht, um 2 Nullen zu garantieren. Nur die Zahlen können durcheinander gewürfelt sein. Nach deinem Vorschlag müssen auf jeden Fall zwei Nullen hintereinander stehen. Du sagst man verlässt den Zustand nur dann wenn zweite Null dann kommt. Ist das richtig?
Man kann das Problem mit e-Übergang lösen, aber irgendwie klappt es trotzdem nicht. Also bitte noch ein Vorschlag!!!
Hilfe!!!!!!!

also hier meine Aufgabe 1. Jedoch VORSICHT, es ist LAtex code. Wenn Ihr wisst was man damit machen kann, dann gut. Ansonsten versteht Ihr es vielleicht trotzdem.
Sorry.
Anmerkung: \perp ist das bottom symbol, die römischen Ziffern sind nur regelnummern(könnt Ihr vergessen).

Viel Spass.

K=(\{0,1\},\{s_{0},s_{1},s_{2},s_{3}\},\{0,1,\perp \},\delta ,s_{0},\{s_{2}\})mit
\delta =\{
(s_{0},1,\perp ,s_{1},0\perp )^{I}, - Liest eine 1ste(oder
weitere) 1 im Fall \#_{1}(w)*2=\#_{0}(w)
ein und schreibt eine Null (von zwei siehe VIII) auf den
Stack.
(s_{0},1,0,s_{1},00)^{II}, - Liest weitere 1sen ein und schreibt
eine Null (von zwei siehe VIII) auf den Stack. Also wenn
\#_{1}(w)*2>\#_{0}(w)
(s_{0},1,1,s_{0},\varepsilon )^{III}, - Liest eine 1 und
löscht eine 1, wenn \#_{1}(w)*2<\#_{0}(w)
(s_{0},0,\perp ,s_{3},\perp )^{IV}, - Liest eine 1ste (oder
weitere) 0 im Fall \#_{1}(w)*2=\#_{0}(w).
(s_{0},0,1,s_{3},1)^{V}, - Liest 0 im Fall \#_{1}(w)*2\leq \#_{0}(w)
und hält den Stack.
(s_{0},0,0,s_{0},\varepsilon )^{VI}, - Liest weitere 0, und
löscht 0, wenn \#_{1}(w)*2>\#_{0}(w).
(s_{0},\varepsilon ,\perp ,s_{2},\varepsilon )^{VII}, - Wechselt
in einen Endzustand , wenn Wort abgearbeitet und Keller
leer. Also auch \#_{1}(w)*2=\#_{0}(w) gilt.
(s_{1},\varepsilon ,0,s_{0},00)^{VIII}, - Schreibt für eine
gelesene 1, die zweite fehlende 0 auf den Keller (siehe
I+II).
(s_{3},1,\perp ,s_{0},0\perp )^{IX}, - Liest eine 1 im Fall
\#_{1}(w)*2+1=\#_{0}(w) und schreibt die nun fehlende 0
(s_{3},1,1,s_{3},\varepsilon )^{X}, - Liest 1 im Fall \#_{1}(w)*2<\#_{0}(w)
und löscht 1 vom Keller (es fehlt eine weniger!).
(s_{3},0,\perp ,s_{0},1\perp )^{XI}, - Liest eine 0 im Fall
\#_{1}(w)*2+1=\#_{0}(w) und schreibt die nun fehlende 1.
(s_{3},0,1,s_{0},11)^{XII}\} - Liest 0 im Fall \#_{1}(w)*2<\#_{0}(w)
und schreibt die fehlende 1 (für jede zweite gelesene 0
in Folge).

Zusatz - Latex:

leq heisst less or equal
geq heisst greater or equal

Idee für
Aufgabe 2e.)

Ich habe leider kein Verfahren gefunden, diese Aufgabe genau
zu lösen. Also muss ich mal etwas schwafeln.
Ich vermute L(G) wird nicht von det. Kellerautomaten erkannt.
Ein Automat muss sich zuerst die Anzahl a auf dem Keller
merken, um festzustellen, ob gleich oder ungleich viele
a und b vorhanden sind. Dies geschieht, wenn der Automat
b gegen a vom Keller löscht. Entweder sind noch a oder b
auf dem Keller, wenn c gelesen werden. Im Fall ungleich
viele a und b, kennt der Automat nicht mehr die gelesene
Anzahl b, um eine korrekte Anzahl c zu erkennen. Zumindest
kann er dieses nicht, wenn er nicht "spontan"
entscheiden kann, ob Anzahl a gleich/ungleich Anzahl b ist.

Also vermute ich s.o.

Nein, so kann man nicht begründen.
Denn es kann ja trotzdem einen DPDA geben. Dieses wird nicht durch die Existenz eines NDPDA ausgeschlossen (Teilmengenbezihehung).