\documentclass[11pt]{article}
\usepackage{alltt}
\usepackage{verbatim}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{pifont}
\usepackage[dvips]{graphics}
\usepackage[dvips]{graphicx}

\parindent=0cm
\oddsidemargin 0.2cm
\evensidemargin 0.2 cm


\textheight 22cm
\textwidth 16.0cm
\title{\bf Examen Prolog  --- ESSI2  \\
{\large( Documents autoris\'es: {\it tous})}}
\author{Michel Rueher}
\date{Mai 1999}

\begin{document}
\maketitle

\begin{enumerate}
\item (2 points)
	Donnez le r\'esultat de la requ\`ete:
\begin	{alltt}
> [A,\_,C|D]=[[a,b,c],d,e,f,g]
\end	{alltt}	

\item (3 points)	
	Soit le  pr\'edicat d\'efini par les clauses :
\begin	{alltt}
appartient(Sous\_liste,Sur\_liste):-
        conc(L1,Sous\_liste,L2),
        conc(L2,L3,Sur\_liste).
\end	{alltt}	
Quel est le comportement de ce pr\'edicat pour un appel
{\tt appartient(S,L)} o\`u {\tt S} est une liste compl\`etement 
instanci\'ee et {\tt L}  une liste dont la taille est connue.
\item (3 points) Ecrire un pr\'edicat {\tt frere(F,X)} qui est vrai si F est le frere de X.\\
Vous devez d\'efinir  les pr\'edicats  que vous  utilisez.
\item (3 points) Programme ``tracassin'' (cf. annexe).
	Quelle est la version la plus efficace?\\
	 Expliquer pourquoi.
\item (3 points) 
	 Ecrire un pr\'edicat {\tt palindrome(L)} qui v\'erifie que la liste L est un palindrome (version ``naive'' et version utilisant les DCG).
On supposera que L est compl\`etement instanci\'ee (cf. exemples ci-dessous).
\small
\begin	{alltt}
> palindrome([e,l,l,e]).        ou   > palindrome([e,l,l,e],[])
yes                                  yes
> palindrome([e,l,l,e,s]).      ou   > palindrome([e,l,l,e,s],[])
no                                   no
> palindrome([l,a,v,a,l]).      ou   >palindrome([l,a,v,a,l],[]).
yes                                  yes
\end	{alltt}	
\normalsize
\item Soit le langage form\'e des mots de la forme $a^nb^n$.
\begin{enumerate}
\item (2 points)	 Utilisez les {\tt DCG} pour analyser les mots de ce langage. 
\item (2 points)	 Donner le programme {\tt prolog} g\'en\'er\'e \`a partir de la {\tt DCG} par l'interpr\`ete {\tt Sicstus};
\item (2 points)	 Donner la {\tt DCG} qui permet d'analyser  les mots de ce langage 
 et de  calculer $n$.\\
\end{enumerate}	
Exemple:
\small
\begin	{alltt}
> anbn(N,[a,a,a,b,b,b],[]).
> N=3
> anbn(N,[a,a,a,b,b],[]).
> no
\end	{alltt}	
\end{enumerate}	

\centerline{Annexe}
\begin	{alltt}
                   /* Tracassin V1 */
tr(P) :-
         etat\_i(E1),  etat\_f(E2),
         transfo(E1,E2,[E1],P).

transfo(Ef,Ef,\_,[]).  
transfo(Ec,Ef,LE,[Op|A]):-
         ope(Ec,Es,Op),
         hors(Es,LE),
         transfo(Es,Ef,[Ec|LE],A).  

ope(E1,E2,r1) :- subst([x,b],[b,x],E1,E2)),!.
ope(E1,E2,r2) :- subst([b,o],[o,b],E1,E2)),!.
ope(E1,E2,r3) :- subst([x,o,b],[b,o,x],E1,E2)),!.
ope(E1,E2,r4) :- subst([b,x,o],[o,x,b],E1,E2)),!.

subst(C1,C2,L1,L2) :-
         conc(L0,R,L1),   conc(X,C1,L0),
         conc(X,C2,Li),   conc(Li,R,L2).

                     /* Tracassin V2 */
tr(P) :-
         etat\_i(E1),  etat\_f(E2),
         transfo(E1,E2,[E1],P).

transfo(Ef,Ef,\_,[]).  
transfo(Ec,Ef,LE,[Op|A]):-
         ope(Ec,Es,Op),
         hors(Es,LE),
         transfo(Es,Ef,[Ec|LE],A).  
ope(E1,E2,r1) :- subst([x,b|L],[b,x|L],E1,E2).
ope(E1,E2,r2) :- subst([b,o|L],[o,b|L],E1,E2).
ope(E1,E2,r3) :- subst([x,o,b|L],[b,o,x|L],E1,E2).
ope(E1,E2,r4) :- subst([b,x,o|L],[o,x,b|L],E1,E2).

subst(L1,L2,L1,L2).
subst(C1,C2,[\_|L1],[\_|L2]) :-
           subst(C1,C2,L1,L2). 
\end	{alltt}	
\small

\end{document}         



