Von Kellerautomat zu Greibach Normalform?
Kann mir ma jemand erklären, wie man hier vorgeht?
Der Kellerautomat soll in Greibach-Normalform überführt werden:
a) Hat der Kellerautomat hier nur einen Zustand?
Was bedeutet das umgedrehte kleine e? Der Übergang(z, a, S) enthält ...(z, ...)?
Übergang(z, a, S) ∋ (z, SBB)
∋ (z, ASB)
∋(z, BB)
∋(z,AB)
Übergang(z,a,A) ∋ (z, epsi)
Man liest im Zustand z ein a, im Keller steht ein großes A, so ließt man dieses große A aus dem Keller aus/weg.
Übergang(z,b,B) ∋ (z, epsi)
Selbe Erklärung nur, das man hier ein B aus dem Keller wegliest.
b) Das Wort aaabbb soll verarbeitet werden.
Kann man hier jemand mal die ersten drei Zeilen erklären. Ich lese ein a aus dem Wort
(z,a,S) -> aSB im Keller steht SBB ??? Was passiert hier?
Ich lese das zweite A aus dem Wort
(z,a,S) -> AB im Keller steht jetzt ABBB?
1 Antwort
Also eigentlich bist du ja schon bei der Greibach Normalform... und sollst jetzt einen Kellerautomaten bauen... oder?
welches „umgedrehte kleine e“? Meinst du die Drei („3“)? oder das „Element von (∋)“ (Mengelehre)?
es hilft dir die Definition des Kellerautomaten... du brauchst einfach nur erst das Tupel mit Platzhaltern hinzuschreiben und dann definierst du die Platzhalter... also die Zustände, die Alphabete, die Zustandsübergangsfunktion, ...
in Teil (b) spielst du dann einfach Kellerautomat und wendest die Zustandsübergangsfunktion an... Zeichen für Zeichen... von links...
also: deine Zustandsübergangsfunktion δ bildet doch auf eine Potenzmenge ab... oder?
also ist der Wert von δ eine Menge... und diese Menge hat Elemente... das umgedrehte ∈ bedeutet einfach „Element von“... da wo es „offen“ ist, steht die Menge...
zu (b): dann zeig mir erstmal dein Z, dein Σ und dein δ... kommt na klar auf dein Kelleralphabet Σ an...
Mehr Informationen hab ich nicht. Ist alles in den Bildern zu sehen
das ist doch gerade deine Aufgabe (a), dass du das Kelleralphabet definierst... und die Funktion δ... oda? steh ich aufm Schlauch...? sowwy... hab das seit etwa 10 Jahren nicht mehr gemacht...
Mir geht es rein um das Verstehen des Vorgehens hier. Man Liest ein Symbol des Wortes und macht gleich etwas auf dem Stack anscheinend hier. Siehe b)
man „macht“ etwas auf dem Stack/Keller, indem man der Zustandsübergangsfunktion den aktuellen Zustand, das nächste Zeichen der Eingabe (oder das leere Wort) und das neueste Zeichen im Keller gibt... man erhält dann den neuen Zustand und die das Wort, das das neueste Zeichen im Keller ersetzen soll... daraus bastelt man sich die aktuelle Konfiguration des Automaten, die aus einem Zustand, einem Eingabewort und einem Kellerwort besteht...
Bitte mal etwas konkreter erklären:
∋ was bedeutet dies bei a)
Das sind die Übergänge
Wie läuft dies bei der b)
Ich habe das Wort aaabbb
(z,a,S) -> SBB Warum steht jetzt hier gleich ein S im Keller?