**_DUPOIS Thomas_**
**_ROUBILLE Mathis_**
**_V. T_**
<p style='text-align: right;'> Année : 2021/2022 </p>
<div style="text-align:center"><img src="https://www.agera.asso.fr/app/uploads/2016/09/logo_isima-300x200.png" /></div>.
# ==TP- Logique L2 info==
#
## ==:memo: 2. Requête et base de connaissance==
##
### 2.1. Introduction
###
1. Vrai, Vincent boit de la vodka
2. La réponse à la requête est "True"
3. Non Otto ne boit pas de la vodka
4. La réponse de l'interpréteur est "False"
5. Oui la réponse à la requête est dorénavant "True"
6. La réponse de l'interpreteur est toutes les personnes qui boivent de l'eau. (réponses : Abdoul, Lhouari, Otto)
7. Linterpreteur donne : X=eau et X=cafe
8.
```c=1
personne(X) :-
boit(X, _).
%Personne est vrai si la personne boit
```
### 2.2 La famille :family: ###
1. Le predicat **mere** est le suivant :
```c=1
mere(X,Y) :-
parent(X,Y),
femme(X).
%mere est vrai si X est un parent de Y et Y est une femme
```
2.
Le predicat **fils** est le suivant :
```c=1
fils(X,Y) :-
parent(Y,X),
homme(X),
X \= Y.
%fils est vrai si Y est parent de X et X est un homme
```
Le predicat **fille** est le suivant :
```c=1
fille(X,Y) :-
parent(Y,X),
femme(X),
X \== Y.
%fille est vrai si Y est parent de X et X est une fille
```
3.
Le predicat **grandpere** est le suivant :
```c=1
grandpere(X,Y) :-
homme(X),
parent(X,Y),
X \== Y,
parent(Y, Z),
Y \== Z,
X \== Z.
%grandpere est vrai si X est un homme et si X est parent de Y et Y parent de Z.
%Sachant que X n'est pas égal à Y , Y n'est pas égal à Z et X n'est pas égal à Y ( on ne peut pas être sois même son grand père).
```
Le predicat **grandmere** est le suivant :
```c=1
grandmere(X,Y) :-
femme(X),
parent(X,Y),
X \== Y,
parent(Y, Z),
Y \== Z,
X \== Z.
%grandmere est vrai si X est une femme et si X est parent de Y et Y parent de Z.
%Sachant que X n'est pas égal à Y , Y n'est pas égal à Z et X n'est pas égal à Y ( on ne peut pas être sois même sa grand mère).
```
4.
Le predicat **soeur** est le suivant :
```c=1
soeur(X,Y) :-
parent(Z,Y),
fille(X,Z),
X \== Y.
%soeur est vrai si Z est parent de Y et X est une fille de Z.
```
Le predicat **frere** est le suivant :
```c=1
frere(X,Y) :-
parent(Z,Y),
fils(X,Z),
X \== Y.
%frere est vrai si Z est parent de Y et X est un fils de Z.
```
5.
Le predicat **cousin** est le suivant :
```c=1
cousin(X,Y) :-
fils(X,Z),
frere(Z,F),
parent(F,Y),
X \== Y.
cousin(X,Y) :-
fils(X,Z),
soeur(Z,S) ,
parent(S,Y),
X \== Y.
%cousin est vrai si X est un fils/fille de Z et que Z est frere/soeur de F/S, ainsi que S est parent de Y.
```
Le predicat **cousine** est le suivant :
```c=1
cousine(X,Y) :-
fille(X,Z),
frere(Z,F),
parent(F,Y),
X \== Y.
cousine(X,Y) :-
fille(X,Z),
soeur(Z,S) ,
parent(S,Y),
X \== Y.
%cousine est vrai si X est un fils/fille de Z et que Z est frere/soeur de F/S, ainsi que S est parent de Y.
```
Voici les arbres généalogiques que l'on a modélisé :
<div style="text-align:center"><img src="https://zupimages.net/up/21/50/t0ko.png" /></div>.
<div style="text-align:center"><img src="https://zupimages.net/up/21/50/l8lz.png" /></div>.
### 2.3 La fin de la solitude ###
1.
Voici quleques faits :
```c=1
personne(007, James Bonde, 183, blond, 68). %l’identifiant 007 correspond à une personne d’1m83, cheveux blond,agé de 68 ans
gout(007, action, scientifique, escalade). %l’identifiant 007 correspond à une personne qui aime les musique d’actions, lire des documents scientifique, et pratique l’escalade).
recherche(007, 168, rose, 28) %l’identifiant 007 correspond à une personne qui recherche une autre personne de taille 1m68, cheveux roses et de 28 ans.
personnes(9, John Deuf, 1.80, jaune, 20).
gout(9, rock ,recetteCulinaire, rugby).
recherche(9, 1.60, blanc, 22).
personnes(10, Ines Spéré, 1.50, chatin, 19).
gout(10, rap, roman, football).
recherche(10, 1.80, blond, 22).
personne(63, Anna Tomie, 1.75, Brune, 25).
gout(63, pop ,articleScientifique, running).
recherche(63, 1.88, Brun, 30).
personne(17052009, Steve, 1.87, Brun, 12).
gout(17052009, Orchestral, Heroic Fantasy, chasse au dragon).
recherche(17052009, 1.88, Roux, 12).
personne(18112011, Alex, 1.88, Roux, 12).
gout(18112011, Orchestral, Science Fiction, Construction).
recherche(18112011, 1.87, Brun, 12).
personne(42, Luffy Ochako Gojo Iida Qulbutoké Uchiwa Endeavor, 2.09, Blond, 42).
gout(42, Tectonique, Realiste, Ultimate Extension).
recherche(42, 1.77, Blond, 38).
```
2.
Le predicat **convient-physiquement** est le suivant :
```c=1
convient-physiquement(X, Y) :-
recherche(Y, T, C, A),
personne(X, _, T, C, A),
X \== Y.
```
**convient-physiquement est vrai si la personne recherchée et la personne en question ont un physique similaire**
Le predicat **ont-memes-gouts** est le suivant :
```c=1
ont-meme-gout(X, Y) :-
gout(X, M, L, S),
gout(Y, M, L, S),
X \== Y.
```
**ont-memes-gouts est vrai si les deux personnes en question ont des goûts similaires**
3.
Le programme qui détermine les couples assortis est le suivant :
```c=1
couple(X,Y) :-
ont-meme-gouts(X,Y),
convient-physiquement(X,Y),
convient-physiquement(Y,X).
```
**couple est vrai si et seulement si, les deux personnes concernées ont d'une part les mêmes goûts, mais aussi, se plaisent physiquement l'un l'autre.**
### 2.4 Attention à ne pas dépasser ! ###
1.
```c=1
couleur(vert).
couleur(jaune).
couleur(rouge).
coloriage(C1, C2, C3, C4) :-
couleur(C1),
couleur(C2),
couleur(C3),
couleur(C4),
C1 \== C2,
C1 \== C3,
C1 \== C4,
C2 \== C3,
C3 \== C4.
```
**D'une part on vérifie que les couleurs sont bien soit verte, jaune ou rouge.
Ensuite selon le schéma donné, on vérifie bien que des couleurs adjacentes ne soient pas similaire.**
2.
Le nouveau predicat est le suivant :
```c=1
couleur(vert).
couleur(jaune).
couleur(rouge).
coloriage(C1, C2, C3, C4) :-
C1 \== C2,
C1 \== C3,
C1 \== C4,
C2 \== C3,
C3 \== C4,
couleur(C1),
couleur(C2),
couleur(C3),
couleur(C4).
```
**Si nous effectuons la requête suivante "coloriage(X,Y,Z,T).", nous obtenons cette fois-ci un résultats différant. Nous avons les mêmes réponses mais en plus nous avons des réponses ne répondant pas au problème que nous traitons.
Cela s'explique du fait que cette fois si la comparaison ce fait avant l'attribution des couleurs aux cases.**
**Donc l'ordre de comparaison a son importance.**
## ==:memo: 3. Graphes et récursivité==
##
### 3.1. Introduction
###
1.
Le code de la **fonction factorielle** est le suivant :
```c=1
fact(0,1).
fact(N,R) :-
N > 0,
Nprec is N-1,
fact(Nprec, Rprec),
R is N*Rprec.
%La fonction fact test si R et le factorielle de N
%elle permet donc d'optenir le factorielle
%d'un nombre n en utilisant fact(n, X).
%Pour cela pour tout N > 0 on multiplit N par le
%factorielle de N-1, ainsi on a une fonction récursive qui
%va remonter jusqu'a 0 qui à une factorielle defini à 1.
```
2.
Le code de la **somme des entiers** est le suivant :
```c=1
somme(1,1).
somme(N,R) :-
N > 0,
Nprec is N-1,
somme(Nprec,Rprec),
R is N+Rprec.
%On note que Nprec = N-1 afin d'obtenir le cas d'arrêt "somme(1,1).", ensuite, on appelle somme afin de déterminer la valeur Rprec donc R prendra la valeur.
%C'est une fontion récursive donc Rprec prendra lui même la valeur d'un autre Rprec...etc.
%Ainsi R obtient finalement la valeur correspondant à la somme des N nombres entre eux.
```
3.
Le code de la **suite de Fibonacci** est le suivant :
```c=1
fibo(0,0).
fibo(1,1).
fibo(N,R) :-
N > 0,
Nprec is N-1,
Nprecbis is N-2,
fibo(Nprec,Rprec),
fibo(Nprecbis,Rprecbis),
R is Rprec + Rprecbis.
%Afin d'obtenir la suite de Fibonacci en prologue, on prend comme cas d'arrêt "fibo(0,0)." ou "fibo(1,1).".
%Nprec prend la valeur de N-1 et NprecBis la valeur de N-2, comme pour la somme des nombres, on rappel la fonction Fibo avec N-1 et N-2, ce qui va permettre de définir Rprec et RprecBis.
%On sait que pour la fonction de fibonacci N = N-1 + N-2. C'est pourquoi R = R-1 + R-2.
```
4.
Le code de la **fonction Ackerman** est le suivant :
```c=1
ackermann(0, N, R) :-
R is N+1.
ackermann(M, 0, R) :-
M > 0,
M2 is M-1,
ackermann(M2, 1, R).
ackermann(M, N, R) :-
M > 0,
N > 0,
M2 is M-1,
N2 is N-1,
ackermann(M, N2, R1),
ackermann(M2, R1, R).
%On défini d'abord que ackermann avec m=0 donne N+1, que ackerman
%avec N = 0 donne ackermann de (m-1, 1) et que dans les autres cas
%on aura ackermann de (m-1, ackermann de (m, n-1)).
%Avec son on peut donc trouver le resultats de la fonction ackermann
%pour tout couple x, y avec ackermann(x, y, X).
```
### 3.2. Graphes dirigés acycliques
###
1.
Le predicat **chemin-oriente** est le suivant :
```c=1
arete(a, b).
arete(b, d).
arete(b, c).
arete(a, c).
%Déclaration des aretes (lien entre chaque sommets).
chemin-oriente(X,Y) :-
arete(X,Y).
%chemin-oriente(X,Y) est vrai si il existe une arete reliant X et Y.
chemin-oriente(X,Y) :-
arete(X,Z),
chemin-oriente(Z,Y).
%chemin-oriente(X,Y) est vrai pareillement si (par transitivité) il existe une arete entre X et Y et une arete entre Y et Z, par conséquent, X et Z forme un chemin.
%(on peut observer des cas de transitivités multiples).
```
2.
Le nouveau predicat **chemin-orienteBis** est le suivant :
```c=1
arete(a, b).
arete(b, d).
arete(b, c).
arete(a, c).
chemin-orienteBis(X,Y,1) :-
arete(X,Y).
chemin-orienteBis(X,Y,N) :-
arete(X,Z),
N1 is N-1,
chemin-orienteBis(Z,Y, N1).
%On se trouve dans le même cas que précédément, néanmoins on recherche un chemin orienté avec un nombre d'aretes précises.
%Ainsi, on rajoute un paramètre N, qui permettra de définir un cas d'arrêt.
%Puis on appelle récursivement la fonction "chemin-orienteBis" en testant avec l'ensemble des aretes de X ("arete(X,Z)").
%Cela nous permet de tester l'ensemble des possibilités.
```
3.
```c=1
sommet(a).
sommet(b).
sommet(c).
sommet(d).
sommet(y).
sommet(z).
%Ensemble de sommets
arete(a,b).
arete(b,d).
arete(b,c).
arete(a,c).
arete(y,z).
%Ensemble des aretes
chemin(X,Y) :-
arete(X,Y); arete(Y,X).
%chemin(X,Y) est vrai s'il existe une arete soit (X,Y) soit (Y,X)
%En effet, on teste s'il existe un chemin orienté dans les deux sens car on recherche l'ensemble des chemins connectés et non pas orientés.
chemin(X, Y) :-
(arete(Z,Y); arete(Z,X)), chemin(X,Z).
%On cherche l'ensemble des points formants des aretes avec X et Y afin de tester toutes les possibilités.
connectSommet(A, [A]).
%Chemin entre un sommet et lui même.
connectSommet(A, [A|Q]) :-
connectSommet(A, Q).
%Comparaison d'un sommet avec lui même
connectSommet(A, [X]) :-
chemin(A, X).
connectSommet(A, [H|Q]) :-
chemin(A, H), connectSommet(A, Q).
%Cela permet de vérifié l'existebce d'un chemin entre un sommet et une liste de sommets.
compareListes([X], L1) :-
connectSommet(X, L1).
compareListes([H|Q], L1) :-
connectSommet(H, L1),
compareListes(Q, L1).
%Permet d'effectuer l'ensemble des tests de comparaisons entre les listes de sommets et les sommets existant.
connecte(L) :-
compareListes(L, L).
```
## ==:memo: 4. Listes et langues==
###
### 4.1. Introduction
###
1.
La réponse de l'intepreteur est :
```
X = a,
Y = [b, c, d]
```
X est la tête de la liste, tandis que Y est le corps (ou la tête).
2.
La réponse de l'intepreteur est :
```
false
```
Effectivement, l'interpreteur ne peux pas grâce à une unique variable lui associé 4 valeurs.
Autrement dit la requête correcte serait "[X,Y,Z,T] = [a, b, c, d]".
### 4.2. Operations sur les listes
###
1.
Le code du prédicat qui **renvoie le premier élément de la liste** L est le suivant :
```c=1
head(X, [X|_]).
% on regarde si X est dans la tête, obtenue après factorisation du code
```
2.
Le code du prédicat qui **ajoute un élément X au début de la liste** L est le suivant :
```c=1
addhead(X, L, [X|[L]]).
```
3.
Le code du prédicat qui **renvoie le dernier élément de la liste** L est le suivant :
```c=1
last(X, [X]).
last(X, [_ | Q]) :-
last(X, Q).
/* supprime à chaque fois la tête jusqu'à ce qu'il ne reste plus que un élément*/
```
4.
On a ```Résultat = [[a,b,c,d]|e] ```
Le problème ici est que la tête de liste est composée de plusieurs éléments et la queue en revanche que d'un seul.
Pour remédier à ce problème, nous proposons le code suivant :
```c=1
addlast(X, [], [X]).
addlast(X, [H | Q], [H | W]) :- addlast(X, Q, W).
%Si la liste est vide il renvoi une liste avec seulemment X.
%Sinon on prend la liste sans le premiére élemment et on recommence
%jusqu'a être au dérnière élemment.
```
5.
Le code du prédicat **pour renverser une liste** est le suivant :
```c=1
/* on gere le cas particulier :
l'inverse d'une liste vide est une liste vide*/
reverse([],[]).
/*
* il faut mettre le premier element de la liste à la fin du reste de la liste inversée
*/
reverse([X|Y], Z) :-
reverse(Y,ZBis),
append(ZBis, [X], Z).
```
### 4.3. Construction inductive et languages
###
#### Language 1 : $a^nb$
Soit L1 le langage tel que tous ces mots soit de la forme $a^nb$.
On peut consruire ce langage à partir de la règle inductive suivante (S est un mot sur {a,b}) :
Base : $b \in L1$
R1 : $S \in L1 \rightarrow aS \in L1$
```c=1
/* le mot avec seulement un b est un mot valide (base) */
langage1([b]).
/*
* si on ajoute un 'a' à la liste, cela reste un mot du langage
* on le place comme tete de liste
*/
langage1([a|S]) :-
langage1(S).
```
#### Language 2 : $ab^n$
Soit L2 le langage tel que tous ces mots soit de la forme $ab^n$.
On peut consruire ce langage à partir de la règle inductive suivante (S est un mot sur {a,b}) :
Base : $a \in L2$
R1 : $S \in L2 \rightarrow Sb \in L2$
```c=1
/* le mot avec un seul a est le plue petit mot du langage*/
langage([a]).
/*
* si abS est un mot alors aS est un mot
* methode permettant de construire les mots du langage
*/
langage([a, b | S]) :-
langage([a | S]).
```
#### Language 3 : $a^nb^m$
Soit L3 le langage tel que tous ces mots soit de la forme $a^nb^m$. Et soit z le mot vide.
On peut consruire ce langage à partir des règles inductives suivantes (S est un mot sur {a,b}) :
Base : $z \in L3$
R1 : $S \in L3 \rightarrow aS \in L3$
R2 : $S \in L3 \rightarrow Sb \in L3$
```c=1
/*
* plusieurs cas "de mots de bases"
* seulment a
* seulement b
* seulement ab
*/
langage3([]).
langage3([a]).
langage3([b]).
langage3([a,b]).
/* methode permettant de construire les mots */
/* si aaS est un mot alors aS est un mot (on applique R1 retrospectivement) */
langage3([a, a|S]):-
langage3([a | S]).
/* si bbS est un mot alors bS est un mot (on applique R2 retrospectivement) */
langage3([b, b|S]):-
langage3([b | S]).
/* si le mot commence par un 'a' et il ect composé de plusieurs 'b', on supprime le premier 'b' (on applique R2 retrospectivement) */
langage3([a, b, b| S]) :-
langage3([a, b |S]).
```
#### Language 4 : $a^{2n}$
Soit L4 le langage tel que tous ces mots soit de la forme $a^{2n}$. Et soit z le mot vide.
On peut consruire ce langage à partir de la règle inductive suivante (S est un mot sur {a,b}) :
Base : $z \in L5$
R1 : $S \in L4 \rightarrow aaS \in L4$
```c=1
/* le mot vide appartient au langage */
langage([]).
/* si on a un mot qui commence par 2 'a' on supprime les deux (on applique R1 retrospectivement) */
/*
* si il n'y a que des 'a' alors et un nombre pair de fois on obtient une liste vide
* si il nous reste un seul 'a' alors le mot n'appartient pas au langage
* si on obtient une (ou plusieurs) autre(s) lettre(s) alors le mot n'appartient pas au langage
*/
langage([a, a| S]) :-
langage(S).
```
#### Language 5 : $a^nb^n$
Soit L5 le langage tel que tous ces mots soit de la forme $a^nb^n$. Et soit z le mot vide.
On peut consruire ce langage à partir de la règle inductive suivante (S est un mot sur {a,b}) :
Base : $z \in L5$
R1 : $S \in L5 \rightarrow aSb \in L5$
```c=1
/* le predicat addlast a été réalisé dans l'exercice précédent, pas de commentaire dessus*/
addlast(X, [], [X]).
addlast(X, [H | Q], [H | W]) :-
addlast(X, Q, W).
/* le mot vide est le plus petit mot du langage */
langage5([]).
/*
* si la liste commence par un a (tete de la liste est 'a') alors
* on verifie que b se trouve à la fin de la liste grace au predicat addlast
* si c'est toujours le cas on supprime le 'a' et le 'b'
*
* A la fin si nous obtenons la liste vide alors le mot appartient au langage
* sinon il n'appartient pas (pas le même nombre de a que de b ou lettre qui n'est pas dans S)
*/
langage5([a | S]) :-
addlast(b, L, S),
langage5(L).
```
#### Language 6 : les palindromes
Soit L6 le langage tel que tous ces mots soit des palindromes. Et soit z le mot vide.
On peut consruire ce langage à partir des règles inductives suivantes (S est un mot sur {a,b}) :
Base : $z \in L6$
R1 : $S \in L6 \rightarrow aSa \in L6$
R2 : $S \in L6 \rightarrow bSb \in L6$
```c=1
/*mote de base*/
langage6([]).
langage6([a]).
langage6([b]).
%Cas d'arrêt, si on obtient une liste vide, un a ou un b, alors c'est un palindrome.
langage6([a|Xs]):-
append(Xs1,[a],Xs),
langage6(Xs1).
langage6([b|Xs]):-
append(Xs1,[b],Xs),
langage6(Xs1).
%on concatene la variable Xsl et (a ou b) dans une même liste nommé Xs, puis par récursivité, on rappel de nouveau la fonction "langage6" jusqu'à retomber sur un des cas d'arrêt.
```
#### Language 7 : $a^lb^mc^n$
Soit L7 le langage tel que tous ces mots de la forme $a^lb^mc^n$. Et soit z le mot vide.
On peut consruire ce langage à partir des règles inductives suivantes (S est un mot sur {a,b}) :
Base : $z \in L7$
R1 : $S \in L7 \rightarrow aS \in L7$
R2 : $S \in L7 \rightarrow Sc \in L7$
R3 : $a^lb^{m-1}c^n \in L7 \rightarrow a^lb^{m}c^n \in L7$
```c=1
/* mots de base*/
langage7([]).
langage7([a]).
langage7([b]).
langage7([c]).
langage7([a,b]).
langage7([b,c]).
langage7([a,c]).
langage7([a,b,c]).
/* si on a le schéma aaS on supprime un 'a' (on applique R1 retrospectivement) */
langage7([a, a|S]):-
langage7([a | S]).
/* si on a le schéma bbS on supprime un 'b', on applique un cas particulier de R3 retrospectivement, celui ou il n'y a pas ou plus de 'a' */
langage7([b, b|S]):-
langage7([b | S]).
/* si on a le schéma ccS on supprime un 'c', on applique un cas particulier de R3 retrospectivement, celui ou il n'y a pas ou plus de 'a' ni de 'b' */
langage7([c, c|S]):-
langage7([c | S]).
/* enleve le 'b' si il y a un seul 'a', le nombre de 'a' à diminuer grace au predicat langage7([a,a|S]) */
langage7([a, b, b| S]) :-
langage7([a, b |S]).
/*
* les predicats restants sont aussi des cas particuliers, on a diviser le porblème afin de faire que des petits portions de codes "facile"
* les predicats suivant suivent le même resonnement que précédemment
*/
langage7([a, c, c| S]) :-
langage7([a, c |S]).
langage7([b, c, c| S]) :-
langage7([b, c |S]).
langage7([a, b, c, c| S]) :-
langage7([a, b, c |S]).
```
#### Language 8 : $a^mb^nc^m$
Soit L8 le langage tel que tous ces mots de la forme $a^mb^nc^m$. Et soit z le mot vide.
On peut consruire ce langage à partir des règles inductives suivantes (S est un mot sur {a,b}) :
Base : $z \in L8$
R1 : $S \in L8 \rightarrow aSc \in L8$
R2 : $a^mb^{n-1}c^m \in L8 \rightarrow a^mb^{n}c^m \in L8$
```c=1
/* prédicats codée dans l'exexercice précédent */
head(X, [X|_]).
addlast(X, [], [X]).
addlast(X, [H | Q], [H | W]) :-
addlast(X, Q, W).
/* le mot vide est un mot appartenant au langage*/
langage8([]).
/* Si S est un mot alors il est forcement constitué de 0 'a' au debut et 0 'c' à la fin , sinon de x 'a' au début et x 'c' à la fin
* on verifie donc que si la tête est un a et si oui si il y a un 'c'*/
langage8(S) :-
addlast(c,[a|S1],S),
langage8(S1).
/*Si le mot commence par 'b' alors on le supprime*/
langage8([b|S]) :-
head(b,S),
langage8(S).
/* à la fin nous devons retomber sur les mots de bases ou sinon il n'appartient pas à l'alphabet*/
```
#### Langage 9
Soit L9 le langage tel que tous ces mots contienent au maximum un b. Et soit z le mot vide.
On peut consruire ce langage à partir des règles inductives suivantes (S est un mot sur {a,b}) :
Base : $z \in L9$
R1 : $(S \in L9$ et $S\backslash\lbrace{b}\rbrace) \rightarrow bS \in L9$
R2 : $(S \in L9$ et $S\backslash\lbrace{b}\rbrace) \rightarrow Sb \in L9$
R3 : $S \in L9 \rightarrow aS \in L9$
R3 : $S \in L9 \rightarrow Sa \in L9$
```c=1
/* predicat qui va nous permettre de savoir combien de b il y a dans le mot*/
compteb([], 0).
/*
* on regarde si 'b' est dans la tete ,
* si oui on increment le deuxième paramètre de la fonction (variable mémoire)
* et on rappelle la fonction sur la queue de la liste
*/
compteb([H | Q], XB) :-
H == b,
compteb(Q, XB1),
XB is XB1+1.
/* cette fois-ci, si c'est 'a' qui est tête alors on n'increment pas le nombre de 'b' trouvé */
compteb([H | Q], XB) :-
H == a,
compteb(Q, XB1),
XB is XB1.
/* mot de base*/
langage9([]).
/* est un mot si il y a un 'b'*/
langage9(L) :-
compteb(L, X),
X == 1.
/* est un mot si il y a 0 'b'*/
langage9(L) :-
compteb(L, X),
X == 0.
/* si on ne se trouve pas dans un de ces 2 cas, alors il y a plus q'un 'b' donc il n'appartient pas au langage*/
```
#### Langage 10
Soit L10 le langage tel que tous ces mots contienent le même nombre de a que de b. Et soit z le mot vide.
On peut consruire ce langage à partir des règles inductives suivantes (S est un mot sur {a,b}) :
Base : $z \in L10$
R1 : $S \in L10 \rightarrow abS \in L10$
R2 : $S \in L10 \rightarrow baS \in L10$
R3 : $S \in L10 \rightarrow Sab \in L10$
R4 : $S \in L10 \rightarrow Sba \in L10$
R5 : $S \in L10 \rightarrow aSb \in L10$
R6 : $S \in L10 \rightarrow bSa \in L10$
```c=1
/*
* compte le nombre de 'a' et de 'b'
* cas particulier pour le mot vide il y a '0' a et '0' b
*/
compte([], 0, 0).
compte([H | Q], XA, XB) :-
H == a,
compte(Q, XA1, XB1),
XA is XA1+1, /*le 'a' a été trouver 2 ligne plus haut , donc on l'incrémente*/
XB is XB1.
compte([H | Q], XA, XB) :-
H == b,
compte(Q, XA1, XB1),
XA is XA1,
XB is XB1+1./*le 'b' a été trouver 3 ligne plus haut , donc on l'incrémente aussi*/
/*on appelle notre predicat compte et on regarde si il y a le même nombre de 'a' que de 'b' autrement dit s X1==X2*/
langage10(L) :-
compte(L, X1, X2),
X1 == X2.
```
#### Langage 11 $a^nb^nc^n$
Soit L11 le langage tel que tous ces mots de la forme $a^nb^nc^n$. Et soit z le mot vide.
On peut consruire ce langage à partir de la règle inductive suivante :
Base : $z \in L11$
R : $a^{n-1}b^{n-1}c^{n-1}\in L11 \rightarrow a^nb^nc^n \in L11$
```c=1
/* predicat de l'exercice précédent */
head(X, [X|_]).
/* predicat de l'exercice précédent*/
addlast(X, [], [X]).
addlast(X, [H | Q], [H | W]) :-
addlast(X, Q, W).
/*Compte le nombre de a Ou de b selon si X=a ou X=b*/
instance([],_,0).
instance([X|L],X,N) :-
instance(L,X,N1),
N is N1+1.
/* Une fois que la tête de liste ne correspond plus à la valeur de X
* Si et seulement si X n'est pas égal à Y, cela signifie qu'on rappel instance avec la queu de liste
* afin de vider la liste peu à peu, jusqu'à tomber sur le cas d'arrêt.
* Néanmoins si X == Y alors il n'y a pas le même nombre de A que de B et la condition est fausse.*/
instance([Y|L],X,N) :-
X\==Y,
instance(L,X,N).
l(M):-
instance(M,a,N), /* compte le nombre de 'a' */
instance(M,b,N). /* compte le nombre 'b' */
/* si l'élément 'b' appartient à la liste (et il est tout seul) ==> cas d'arret*/
langage_l([b]).
langage_l(S) :-
addlast(c,[a|Sbis],S), /* on ajoute 'c' à la fin de S*/
langage_l(Sbis). /* on rappelle la liste sans la tête et le dernier élément cad sans le 'a' et sans le 'c' que l'on a ajouter précédemment */
langage_l([b|S]) :-
head(b,S),
langage_l(S).
/* mot vide appartient au langage*/
langage11([]).
/* si langage_l sur la lsite est vrai*/
langage11(S):-
langage_l(S), /* autant de 'a' que de 'c' */
l(S). /* Si les deux instances sont vrais */
```
Sign in with Wallet
Connect another wallet