48 lines
1.2 KiB
Prolog
48 lines
1.2 KiB
Prolog
% 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, [#], _, [], []). |