% Startzustand des PDA
start(z).

% Zustände
state(z).

% Eingabealphabet
sigma(a).
sigma(b).

% Kelleralphabet
gamma(a).
gamma(b).
gamma(#).

% Übergangsfunktion: delta(FromState, ReadSymbol, PopSymbol, ToState, PushSymbols)
delta(z, a, a, z, []).
delta(z, b, b, z, []).
delta(z, nix, #, z, [a, #, b, #]).
delta(z, nix, #, z, [b, #, a, #]).
delta(z, nix, #, z, []).

% sigma_stern: Akzeptiert leere Eingabe oder Eingabe, die aus Symbolen des Eingabealphabets besteht
sigma_stern([]).
sigma_stern([W|Ws]) :- sigma_stern(Ws), sigma(W).

% Einzelschrittrelation es
es(S, [W|Ws], [Top|Stacks], NewS, Ws, NewStacks) :-
    delta(S, W, Top, NewS, ToStacks),
    append(ToStacks, Stacks, NewStacks).

es(S, Ws, [Top|Stacks], NewS, Ws, NewStacks) :-
    delta(S, nix, Top, NewS, ToStacks),
    append(ToStacks, Stacks, NewStacks).

% Transitiver Abschluss es_plus
es_plus(S, Ws, Stacks, NewS, NewWs, NewStacks) :-
    es(S, Ws, Stacks, NewS, NewWs, NewStacks).

es_plus(S, Ws, Stacks, NewS, NewWs, NewStacks) :-
    es(S, Ws, Stacks, S1, W1, NewStack1),
    es_plus(S1, W1, NewStack1, NewS, NewWs, NewStacks).

% Akzeptanzbedingung
lvonM(Ws) :-
    sigma_stern(Ws),
    start(S),
    es_plus(S, Ws, [#], _, [], []).