Solutions et commentaires.

Cette section sera longue, car son but n'est pas que vous donner les solutions des exercices, mais constituer encore un fragment de mon tutoriel DCG / Prolog.

Commençons par la "devinette posée en TP. Je vous ai proposé l variante de "(a|b)*": 

starab --> [] | ([a]|[b]),starab.
La question était : si on lance phrase(parab,L)., avec la séquence - cible (ou sujet) de l'analyse étant une variable Prolog non-instanciée, donc une variable-réponse, Prolog essaie d'unifier (assigner, metre en correspondance, identifier, apparier...) L avec les constructions internes défissant starab, donc la liste vide, et sinon, a suivi de l'instance de starab qui peut être vide, ou ... etc. Le programme synthétise la séquence-réponse. La réponse non-déterministe (multiple, quand l'utilisateur la force par ";") est : 
 ?- phrase(starab,L).
L = [] ;
L = [a] ;
L = [a,a] ;
L = [a,a,a] ;
L = [a,a,a,a] ;
L = [a,a,a,a,a] 
...
et on ne verra jamais "b". La , raison est que Prolog cherche une nouvelle réponse par le backtracking, le retour en arrière, en reprenant la dernière alternative non-épuisée. Ce backtracking est un mécanisme beaucoup pkus universel que les solutions Prolog, il est utilisé très extensivement dand l'Intelligence Artificielle, et les jeux stratégiques.
Ici, cette dernière alternative est toujours l'alternative entre liste vide - non-vide, la première barre, car le retour relance starab, et non pas "a ou b". La solution consiste à effectuer le choix "a ou b" à la fin de la génération / reconnaissance. Avec : 
starab --> [] | [Ch],starab,{Ch=a;Ch=b}.

 ?- phrase(starab,L).
L = [] ;
L = [a] ;
L = [b] ;
L = [a,a] ;
L = [b,a] ;
L = [a,b] ;
L = [b,b] ;
L = [a,a,a] ;
L = [b,a,a] ;
L = [a,b,a] ;
L = [b,b,a] ;
L = [a,a,b] 
...
nous aurons la réponse voulue.

Vous pouvez poser la question : ne peut-on pas demander la génération de toutes (ou plusieurs, ici "toutes" est infini...) réponses d'un seul coup ? Cherchons d'abord une solution partielle, toutes les réponses de longueur 4. Attention, cette "solution" est mauvaise ! On engendra les 16 instances, et ensuite on boucle sans fin, car la longueur 5 étant mauvaise, le système continue, trouve la longueur 6, puis 7, etc. ... Voici le prédicat et son usage : 
test(L):-phrase(starab,L),length(L,4).

 ?- test(L).
L = [a,a,a,a] ;
L = [b,a,a,a] ;
...
L = [a,b,b,b] ;
L = [b,b,b,b] ;
% et le système plante (boucle sans réponse).
Pour résoudre le dilemme il faut un mécanisme "hard" permettant de dire à Prolog : "assez, ne cherche plus rien !". Ce mécanisme s'appelle "cut", est symbolisé par le point d'exclamation et quand Prolog passe de gauche à droite par le cut, il est invisible. Par contre, lors du backtracking, quand Prolog retourne en arrière, le cut stoppe le processus. Voici la solution, accessoirement définissons, pour votre instruction, le prédicat length(L,N) qui unifie la valeur de N avec la longueur de L : length([a,v,c],M) donne M=3. 
leng([],0).
leng([_|Q],N):-leng(Q,M),N is M+1.

test1(L):-phrase(starab,L),leng(L,M),(M>4,!,false;M=4).
Analysez la solution : quand M<=4, le programme échoue sur M>4, et cherche des alternatives. Si M<4, on retourne vers phrase, pour la valeur 4, on termine avec succès. Par contre si M dépasse 4, on passe par le cut et on "meurt". Plus de réponses....

Et voici comment retourner toutes les solutions d'un prédicat dans une liste. 
toutes(L) :- findall(Rep,test1(Rep),L).

 ?- toutes(A).
A = [[a,a,a,a],[b,a,a,a],[a,b,a,a],[b,b,a,a],[a,a,b,a],[b,a,b,a],[a,b,b,a],[b,b,b,a],[a,a,a,b],
 [b,a,a,b],[a,b,a,b],[b,b,a,b],[a,a,b,b],[b,a,b,b],[a,b,b,b],[b,b,b,b]].
Le prédicat findall (et quelques autres, comme bagof et setof) ramasse des solutions alternatives dans une séquence.

Pour terminer, une question très "perverse". Qu'est-ce que l'on obtient en exécutant : leng(Kezako,5).

Exercice 1.

1. Nombres réels.
Tout d'abord, la reconnaissance d'un chiffre par [0]|[1]| ... |[9] est possible, mais pénible, imaginez la reconnaissance des lettres de cette manière... En Prolog vous avez plusieurs utilitaires pour la reconnaissance de caractères, un de plus simple est le test : char_type(C,digit), qui répond oui, si C= '0', ou '1', ou '2', etc. Pour les nombres 0, 1, 2, ... ceci est faux, les nombres ne sont pas des caractères, comme dans [presque] tout autre langage de programmation. Ce prédicat est par excellence "Prologien", il peut agir aussi comme un générateur, l'apel char_type(Quoi,digit) retourne les caractères en question (et quelques autres, comme '¹', '²', et '³'.

Si on veut, on peut écrire un prédicat comme ça soi-même, a l'aide de char_code(Chr,Nval) qui établit la relation entre un atome/caractère, et son code ANSI, par ex. '1' vaut 49. Mais si le testeur 

chiffre(X):-char_code(X,N),N>=48,N<58.
est trivial, faire un générateur non-déterministe, qui donne les réponses légales à chiffre(X) – un peu moins. C'est un exercice assez fondamental, mais avancé. Nous avons en Prolog le prédicat between(Début,Fin,X), qui unifie X avec toutes les valeurs entre Début et Fin. (On peut le définir comme 
between(Deb,Deb,Deb) :- !. % Évite l'échec final.
between(Deb,Fin,Deb) :- Deb<Fin.
between(Deb,Fin,X) :- Deb<Fin, D1 is Deb+1, between(D1,Fin,X).
si on veut jouer...)
et ensuite 
chiffre(X):-between(48,57,N),char_code(X,N).
Attention. Si nous n'avons pas besoin de la génération non-déterministe, seulement de la vérification, la première solution est considérablement plus efficace.

Finalement, la solution de l'exercice, avec le paramétrage permettant de récupérer le résultat. Notez que si le point est absent, on ne doit pas chercher une seconde séquence de chiffres ! 
sig([]) --> [].
sig([X]) --> [X],{X='+';X='-'}.

reel(Y) --> sig(S),chiffres(A),{append(S,A,A1)},
	(['.'],chiffres(B),{append(A1,['.'|B],Y)} | {Y=A1}).
Le prédicat append est la concaténation des listes comme '+' en Python. Vous pourrez le faire vous-mêmes, analysez le programme ci-dessous : 
append([],L,L).
append([X|Q],L,[X|R]):-append(Q,L,R).

2. Listes, le calcul de la longueur. 

longr(0) --> [].
longr(N) --> [_], longr(M),{N is M+1}.

Exercice 2.

1. Grammaire pour des "listes", par ex. ['[',a,',',a,',',b,',',schtroumpf,']']. L'exercice est très facile, il faut cependant interdire des "éléments" étant les virgules ou les crochets fermants. C'est une occasion d'introduire l'opérateur de négation : (\+). 

atm --> [X],{\+ member(X,[']',','])}.
ll --> ['['],(atm,seql | []),[']'].
seql --> [','],atm,seql | [].

2. La grammaire engendre 192 = 4*4*3*4 phrases. Avec findall vous pouvez synthétiser toutes ces phrases hautement intellectuelles.
Les erreurs évidentes sont : l'article précédent un nom propre, "le Jean" n'est pas correct. Il n'y a pas d'élision de "e", "le acarien" est également mauvais. Afin de corriger ceci, la grammaire doit disposer d'une sous-couche lexicale, capable d'analyser la structure des mots. Ceci n'est pas difficile, mais fatigant...

Exercice 2.

1. Le langage "an bn". La réponse se trouve dans les notes de cours : 

anbn --> [a], [b].
anbn --> [a], anbn, [b].
La récursivité imbriquée signifie que l'automate en question devrait compter toutes les occurrences de "a", avant de réduire le compteur en consommant "b". Or, les automates finis n'ont pas de compteurs de capacité quelconque.

2. La solution est assez simple, il suffit de paramétrer un prédicat : 
nom(X) --> [X],{member(X,[chien,'Jean',président,acarien])}.
...
sent   --> artind,nom(X),optadj,verbe,artdef,nom(X).
La valeur de la variable X doit figurer deux fois dans la phrase. Prouvez que le nombre de phrases possibles se réduit à 48.