% Im Folgenden ist ein nichtdeterministischer endlicher Automat beschrieben
% durch Angabe seiner Uebergangsrelation  delta  und seiner Endzustaende.
% Der Anfangszustand sei q0.
% Auf die Anfrage
%    ?- akz(W).
% gibt dieses Prolog-Programm bei wiederholter Eingabe eines Strichpunkts
% nacheinander alle vom Automaten akzeptierten Woerter aus, jeweils
% dargestellt als Liste von Zeichen.


delta(q0,a,q1).
delta(q0,a,q2).
delta(q0,b,q3).
delta(q1,a,q2).
delta(q1,b,q3).
delta(q2,a,q3).
delta(q2,b,q1).
delta(q3,a,q3).
delta(q3,b,q3).

endzustand(q1).
endzustand(q2).


% l(W,Q) bedeutet:
% Der Automat kann vom Zustand Q aus durch Eingabe des Wortes W
% in einen Endzustand uebergehen. (Also W Element von Lq)
l([],Q) :- endzustand(Q).
l([X|W],Q) :- l(W,P), delta(Q,X,P).


% akz(W) bedeutet: Der Automat akzeptiert das Wort W.
akz(W) :- l(W,q0).



% P.S.: Wenn Sie die Ausgabe als Prolog-Atom (z.B. aab statt
% [a, a, b]) bevorzugen, dann stellen Sie bitte die Anfrage
%   ?- a(A).
% ebenfalls mit wiederholter Eingabe des Strichpunkts.
% Dabei ist das Praedikat a folgendermassen definiert:
a(A) :- akz(W), atom_chars(A,W).
