%------------------------------------------------------------
% Implementacion de diferentes automatas
%
% Autor: Fernando Barber
% Fecha: 5-4-2005
%------------------------------------------------------------

% Las cadenas de entrada son listas donde cada elemento representa
% un simbolo.
% Por ejemplo, la cadena 'abaa' serķa [a,b,a,a]

% El estado final se ha dejado como parametro para que sea
% sencillo averiguar en que estado se ha quedado el automata
% simplemente pasando una variable.
% Si queremos que el automata simplemente acepte o no basta
% con pasarle el estado final en dicho parametro.

%------------------------------------------------------------
% Automata finito no determinista
%------------------------------------------------------------

% af(+ Estado inicial, +Cadena de entrada, ? Estado final)
af(S, [], S).
af(State, [X|In], End):-
	d(State, X, Next),
	af(Next, In, End).

% Funcion de transicion
% d(? Estado actual, ? Simbolo, ? Estado siguiente)

% Funcion de transicion para automata que reconoce cadenas de
% longitud par con alfabeto {a,b}

d(q0, a, q1).
d(q0, b, q1).
d(q1, a, q0).
d(q1, b, q0).

%------------------------------------------------------------
% Automata con pila no determinista
%------------------------------------------------------------

% ap(+ Estado inicial, +Cadena de entrada, ? Estado final, +Pila)
ap(S, [], S,[]).  % Final exigiendo pila vacia.
%ap(S, [], S,_).  % Final sin exigir pila vacia.
ap(State, [X|In], End, Stack):-
	d(State, X, Stack, Next, NewStack),
	ap(Next, In, End, NewStack).

% Funcion de transicion
% d(? Estado actual, ? Simbolo, ? Cima actual de pila, ? Estado siguiente, ? Nueva cima)

% Funcion de transicion para automata que reconoce cadenas del lenguaje
% {0^n1^n|n>=1} con alfabeto {0,1}
d(q1, 0, [], q1, [a]).
d(q1, 0, [a|L], q1, [a,a|L]).
d(q1, 1, [a|L], q2, L).
d(q2, 1, [a|L], q2, L).
d(q2, 1, [a], q3, []).	% La ultima transicion esta modificada para eliminar la e transicion


%------------------------------------------------------------
% Maquina de Turing con una cinta y 3 movimientos (i, d, n)
%------------------------------------------------------------

%  La cinta es una estructura cinta/2 con dos listas. la cabeza de la segunda
% es donde esta el cabezal. Las listas se van expandiendo automaticamente a
% medida que se utilizan.

% Predicado que inserta la cadena a reconocer en la cinta y llama a la mt.
% begin_mt(+ Estado inicial, + Cadena, ? Estado final)
begin_mt(State, In, End):-
	append(In, _, L),
	mt(State, End, cinta(_,L) ).

% mt(+ Estado inicial, ? Estado final, + Cinta)

% Movimiento a la izquierda
mt(State, End, cinta([Y|L1],[X|L2]) ):-
	(var(X) -> X = bl;true),	% La cinta contiene infinitos blancos
	d_mt(State, X, Next, X2, i),
	mt(Next, End, cinta(L1,[Y,X2|L2]) ).

% Movimiento a la derecha
mt(State, End, cinta(L1,[X|L2]) ):-
	(var(X) -> X = bl;true),
	d_mt(State, X, Next, X2, d),
	mt(Next, End, cinta([X2|L1],L2) ).

% Sin Movimiento 
mt(State, End, cinta(L1,[X|L2]) ):-
	(var(X) -> X = bl;true),
	d_mt(State, X, Next, X2, n),
	mt(Next, End, cinta(L1,[X2|L2]) ).

% Sin funcion de transicion
mt(State, State, cinta(_,[X|_]) ):-
	(var(X) -> X = bl;true),
	not(d_mt(State, X, _, _, _) ).

% Funcion de transicion
% d(? Estado actual, ? Simbolo, ? Estado siguiente, ? Simbolo a escribir, ? Direccion (i, d, n) )
% El simbolo blanco lo representaremos con el atomo 'bl'.

% Funcion de transicion para mt que reconoce cadenas del lenguaje
% {|a|=2n |n>=0} con alfabeto {a,b}
d_mt(q0, a, q1, bl, d).
d_mt(q0, b, q0, bl, d).
d_mt(q0, bl, q2, bl, i).
d_mt(q1, a, q0, bl, d).
d_mt(q1, b, q1, bl, d).