%% Version:  1.1  -  Datum: 1. Juni 2010  -  Datei: tm_biene.pl
%%
%% Theoretische Informatik II - Sommersemester 2010
%%
%% Hausaufgabe 7.5 (Fleissige Biene) - Abgabetermin: 18.06.2010, 11 Uhr
%%
%% Name 1:                         Matrikelnummer:
%% Name 2:                         Matrikelnummer:
%% Name 3:                         Matrikelnummer:
%% Name 4:                         Matrikelnummer:
%%
%% Aufgabe: Konstruieren Sie eine "Fleissige Biene"-Turingmaschine mit
%%          zwei und vier Zustaenden, die eine moeglichst grosse Produk-
%%          tivitaet hat. Der Endzustand wird nicht mitgezaehlt! Das
%%          Bandalphabet enthaelt nur die Symbole B (das Leerzeichen)
%%          und * (eine Blume).
%%
%%          Die Produktivitaet Ihrer Turingmaschine, angesetzt auf das
%%          leere Band, ist der groesste Abstand zwischen zwei Blumen *
%%          der Ausgabe, inklusive dieser Blumen. Sie ist 0, falls die
%%          Turingmaschine nicht anhaelt. So ist, zum Beispiel, die Pro-
%%          duktivitaet der Turingmaschine, die *B**B*BB* auf das Band
%%          schreibt, gleich 9. Als Nebenbedingung darf Ihre Turingma-
%%          schine nicht gleichzeitig eine "Busy Beaver"-Turingmaschine
%%          sein, d.h. die Ausgabe Ihrer Turingmaschine mit zwei bzw.
%%          vier Zustaenden darf keine 4 bzw. 13 Blumen enthalten.
%%
%%          Die Uebergangsfunktion Ihrer fleissigen Biene wird unten
%%          definiert. Sie koennen Ihre Turingmaschine testen, indem Sie
%%          "tm([],q0,[!])." aufrufen. Sie stoppen die Turingmaschine
%%          (sofern notwendig) mit "Ctrl-C". Das Leerzeichen wird durch
%%          das Ausrufezeichen ! repraesentiert.
%%
%% Nuetzliche PROLOG-Kommandos
%%    [<programm>].   laedt die Datei <programm>.pl
%%    make.           laedt das Programm erneut, wenn es geandert wurde
%%    halt.           beendet das PROLOG-System
%%
%% Abgabe:  Senden Sie das Programm mit Ihren getesteten Uebergangs-
%%          funktionen bis zum Abgabetermin per Email an Ihren Tutor.

%% Die Uebergangsfunktion delta(q,X):=(q',X',D) wird in der folgenden
%% Form definiert "delta(q,X,q',X',D).", wobei D entweder 'l' or 'r' ist

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TM 1 - Fleissige Biene mit zwei Zustaenden
%
% Hier steht die von Ihnen definierte Uebergangsfunktion
% (auskommentieren, falls Sie TM 2, siehe unten, testen)

% Hier als Beispiel eine fleissige Biene mit einer Produktivitaet von 2
delta(q0,!, q1,*,l). delta(q0,*, qe,*,r).
delta(q1,!, q0,*,r). delta(q1,*, q1,*,l).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TM 2 - Fleissige Biene mit vier Zustaenden
%
% Hier steht die von Ihnen definierte Uebergangsfunktion
% (auskommentieren, falls Sie TM 1, siehe oben, testen)

% delta(q0,!,  , , ). delta(q0,*,  , , ).
% delta(q1,!,  , , ). delta(q1,*,  , , ).
% delta(q2,!,  , , ). delta(q2,*,  , , ).
% delta(q3,!,  , , ). delta(q3,*,  , , ).

accept([]).

%% Do not change anything below this line except you know
%% what you are actually doing ...
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
tm(A,Q,[X|B]) :-
  print(A), print(Q), print([X|B]), nl,
  delta(Q,X,Q1,X1,D),
  (D=l ->
    (A=[] -> tm([],Q1,[!,X1|B]) ; append(A1,[Y],A), tm(A1,Q1,[Y,X1|B]));
    append(A,[X1],A1), (B=[] -> tm(A1,Q1,[!]) ; tm(A1,Q1,B))
  ).
tm(_,Q,[X|_]) :- \+delta(Q,X,_,_,_), accept(F), member(Q,F).