% Autor:  Manuel Bremer
% aufbauend auf: "Informatik mit PROLOG", Kapitel 18
% Title: Kellerautomaten
% Datum: 16.04.2007

% TEIL A: ALLGEMEINES

% Verwendete Prädikate:               (
% "+" kennzeichnet Eingabe-, "-" Ausgabeparameter)
% kellerautomat(+Zustand, +Eingabeliste, +Keller)
% kellern(+Kelleroperation, +AlterKeller, -NeuerKeller)
% uebergang(+Zustand, +Eingabe, +Kellerelement, -Kelleroperation, -Folgezustand)
% erzeugteSprache(+Wort) prüft ob das Wort zur insgesamt erzeugten Sprache
%                              gehört, beliebige Suchtiefe!
% einfachuebergang(+Zustand,+Eingabe,+AlterKeller,-NeuerKeller, -Folgezustand)
%                  ist eine Variante von uebergang, welche die Zuässigkeit der
%                  Eingabe prüft und dann entsprechende Kelleroperation vornimmt
% mehrfachuebergang(+Zustand,+Eingabe,+AlterKeller,-NeuerKeller, -Folgezustand)
%                  fasst 1 bis beliebig viele einfachuebergang-Schritte zusammen

% Fakten ueber den Automaten:
% alphabet - implementiert ueber eine Liste von Zeichen
% anfangszustand(+BestimmterZustand)
% endzustand(+BestimmterZustand)


% Allgemeine Regeln:
kellerautomat(Zustand, [Eingabe|Rest], [Top|Keller]) :-
                  uebergang(Zustand,Eingabe,Top,Kelleroperation,NeuerZustand),
                  kellern(Kelleroperation,[Top|Keller],NeuerKeller),
                  % Ausgabe des gerade vollzogenen Schrittes
                  write(Zustand), tab(2),
                  write([Eingabe|Rest]), tab(2),
                  write(Top),
                  write(' -> '),
                  write(NeuerKeller), tab(2),
                  write(NeuerZustand),nl,
                  % Aufrufen des nächsten Schrittes
                  kellerautomat(NeuerZustand, Rest, NeuerKeller).
kellerautomat(Endzustand,[],[#]):- endzustand(Endzustand).
kellern(push(Element),Keller,[Element|Keller]).  % Element ablegen
kellern(pop,[_Element|Keller], Keller).   % Topelement beseitigen
                                          % (wird nicht weiter verwendet)
kellern(nop,Keller,Keller).               % Nichtstun

% Auskunft über die Zugehörigkeit eines Wortes zur erzeugten Sprache
erzeugteSprache(Wort) :- anfangszustand(Anfang),
                      mehrfachuebergang(Anfang,Liste,[#],[#],Ende),
                      endzustand(Ende),
                      zusammensetzen(Liste,Wort).
einfachuebergang(Zustand,Eingabe,[KellerTop|Restkeller],NeuerKeller,
   Folgezustand) :- alphabet(Eingabe),
         uebergang(Zustand,Eingabe,KellerTop,Kelleroperation,Folgezustand),
         kellern(Kelleroperation,[KellerTop|Restkeller],Neuerkeller).
mehrfachuebergang(Zustand,[Eingabe],AlterKeller,NeuerKeller,Folgezustand) :-
  einfachuebergang(Zustand,Eingabe,AlterKeller,NeuerKeller,Folgezustand).
mehrfachuebergang(Zustand,[Kopf|Rest],AlterKeller,NeuerKeller,Folgezustand) :-
mehrfachuebergang(Zwischenzustand,Rest,Zwischenkeller,NeuerKeller,Folgezustand),
einfachuebergang(Zustand,Kopf,AlterKeller,Zwischenkeller,Zwischenzustand).

% Zur Prüfung eines Ausdrucks/Inputs aufzurufen (mit Ausdruck der Schritte):
akzeptiere(Wort):-
                  anfangszustand(Zustand),
                  zerlegen(Wort,Eingabeliste),
                  kellerautomat(Zustand,Eingabeliste,[#]).


% TEIL B: SPEZIELLE HILFSPRAEDIKATE
% zerlegen(+Wort,-Buchstabenliste)
% zusammensetzen(+Buchstabenliste,-Wort), Umkehrung von "zerlegen"


zerlegen(Wort,Liste) :- name(Wort,Codes),
                     convert(Codes,Liste).
convert(Codes,Liste) :- Codes = [Anfang|Rest],
                     convert(Rest,Restliste),
                     name(AnfangListe,[Anfang]),
                     Liste = [AnfangListe|Restliste].
convert([],[]).
zusammensetzen(Liste, Wort) :-
                      r-convert(Codes,Liste),
                      name(Wort,Codes).
r-convert(Codes,Liste) :- Liste = [Listenanfang|Listenrest],
                       name(Listenanfang,[CodesAnfang]),
                       Codes = [CodesAnfang|CodesRest],
                       r-convert(CodesRest,Listenrest).
r-convert([],[]).
ziffer(A) :- member(A,[0,1,2,3,4,5,6,7,8,9]).

% TEIL C: VERSCHIEDENE AUTOMATEN   [im Prinzip müssen jeweils die anderen
%                                  auskommentiert oder gelöscht werden]

% C.1  Erkennen der Sprache {n-viele "a" gefolgt von n-vielen "b"}
% Der Keller wird mit "#" initialisiert.
% Ein Wort wird akzeptiert, wenn mit geleertem Keller der Endzustand z1
% auf dem letzten zu lesenden Zeichen erreicht wird

alphabet(X):- member(X,[a,b]).
anfangszustand(z0).
endzustand(z1).
uebergang(z0,a,#,push(a),z0).    % Anfangsschritt
uebergang(z0,a,a,push(a),z0).    % bei Lesen von "a" ein "a" pushen
uebergang(z0,b,a,pop,z1).      % beim ersten "b" Zustand wechseln, "a" poppen
uebergang(z1,b,a,pop,z1).      % bei Lesen von "b" ein "a" poppen

% Beispielaufruf für C.1: ?- akzeptiere(aaabbb).
                  
% C.2  Erkennen von arithmetischen Ausdrücken mit richtiger Klammerung
% Ein arithmetischer Ausdruck wird bei korrekter Syntax akzeptiert, bei
% einfacher Klammerung im Endzustand z1, ansonsten im Endzustand z2

anfangszustand(z0).
endzustand(z1).
endzustand(z2).
uebergang(z0,'(',_,push('('),z0). % linke Klammer gelesen und gekellert
uebergang(z0,Zeichen,_,nop,z1) :- ziffer(Zeichen). % lese beliebige Zahl ein
uebergang(z1,')','(',pop,z2). % passende rechte Klammer gefunden
uebergang(z1,Zeichen,_,nop,z1) :- ziffer(Zeichen). % lese beliebige Zahl ein
uebergang(z1,'+',_,nop,z0). % Operator gefunden
uebergang(z1,'-',_,nop,z0).
uebergang(z2,')','(',pop,z2). % passende äußere rechte Klammer gefunden
uebergang(z2,'+',_,nop,z0). % mit Operator einen weiteren Ausdruck anhängen
uebergang(z2,'-',_,nop,z0).

% Beispielaufruf für C.2: ?- akzeptiere('(4+6)-((2-3)+8)').

% C.3  Erkennen von Palindromen (spiegelsymmetrische Wörter)
% im Zustand z0 werden einfach Zeichen gepusht, dann wird nicht-deterministisch
% in einen Zustand z1 gewechselt, in dem dann zum nun gelesenen Wort dasselbe
% auf der Kellerspitze liegen muss; der Übergang erfolgt in der Mitte des
% Wortes ohne Operation (bei ungerader Länge) oder mit erstem Poppen.
% Ein Palindrom wird akzeptiert, wenn in z1 der Speicher leer wird

anfangszustand(z0).
endzustand(z1).
uebergang(z0,X,_,push(X),z0).
uebergang(z0,_,_,nop,z1). % benötigt für ungerade Länge
uebergang(z0,X,X,pop,z1).
uebergang(z1,X,X,pop,z1).

% Beispielaufruf für C.3: ?- akzeptiere(abaaaaba).