**** Éléments de correction td1-BIS-LT-RICM2 ****
**** Laurent Mounier et Laure Gonnord ****
**** Version 3 - 30 sept 05 ****

Exo 1 
-----

a*b :	(0,a,0)
	(0,b,1) {1} terminal

(aab+aa)* :
	(0,a,1)
	(1,a,0)
	(1,a,2)
	(2,b,0) {0} terminal 
(pas déterministe..)

eps + aa*(aab)*
	(0,a,1)
	(1,a,1)
	(1,eps,2) <--- pour ne pas pouvoir retourner faire des a*...
	(2,a,3)
	(3,a,4)
	(4,b,2)
	{0,2} terminaux

(ce sont des exemples il existe plein de différents)


Exo 2 
-----
1.
à l'aide du td1, on a une notation bnf des constantes entières
signées:
	chiffre_positifs ::= 1 | 2 | ... | 9
	chiffre ::= 0 | chiffre_positif
	lettre ::= a | ... | z | A | ... | Z
	signe ::= + | -
	constante_entiere_sans_signe ::= chiffre_positif.chiffre*
	constante_entiere_signee ::= signe.chiffre_positif.chiffre*
	constante_entiere ::= constante_entiere_sans_signe
	| constante_entiere_signee


on ajoute les monomes pour obtenir les polynomes
	 monome ::= x ^ constante_entiere_sans_signe | x^0
	 polynome ::= constante_entiere * monome | epsilon 


Maintenant, comment fait-on pour "autoriser" les simplifications ?
(attention cela ne veut pas dire que l'on interdit les expressions non
simplifiées ...)

par exemple, 5*x^1==5*x --> on rajoute la possibilité d'avoir x dans
la regle du monome : 
	 monome ::= x ^ constante_entiere_sans_signe | x^0 | x

5*x^0 == 5 modification de la regle du polynome pour obtenir la
suppression du * :
	 polynome ::= constante_entiere * monome | epsilon | constante_entiere

etc etc..

2.
On cree l'automate directement en lisant la grammaire ... il vaut
mieux séparer les bouts reconnaissant les chiffres, les monomes, etc
et leur donner un nom.


Attention, la définition de la notation bnf pourrait laisser penser
que la notation est équivalente aux automates finis, alors que la
notation BNF est UNE façon d'écrire les grammaires hors-contexte. Ce
que l'on donne en cours pour BNF est en fait l'extended BNF
(=grammaire dans laquelle on s'autorise des expressions rationnelles
sur les terminaux et non terminaux à droite....)

3. Éléments de réponse.

Attention la question est ambiguë (eheh). Ce qu'on voulait était :
"existe-t-il un automate fini pour reconnaitre les polynomes par degré
décroissant ?"


Pour reconnaître un polynome par degré croissant, il faudrait trouver
un moyen de mémoriser le degré du dernier monome reconnu, et dans un
automate fini la seule façon de mémoriser est de créer un état par
degré du dernier monome reconnu. Comme les degrés des monomes sont en
nombre infini, il faudrait donc créer un automate avec un nombre
infini d'états, ce qui est impossible. convaincus ?


PLus formellement, faisons cette preuve par "séparation des états"
(on suppose qu'il existe un automate fini déterministe reconnaissant
ce langage. Sans perdre de généralité on le suppose déterministe)

Soit q_n l'état obtenu en lisant x^{2n} à partir de l'état
q_0. On va prouver que forcément q_3<>q_4, en effet en lisant x^7 à
partir de q_3, on doit se trouver dans un état non acceptant, et en
lisant x^7 à partir de q_4, on doit se retrouver dans un état
acceptant. 

Ainsi q_3 <> q_4 <> q_5 etc, on construit donc ainsi un nombre infini
d'états pour l'automate, ce qui est impossible.