**** éléments de correction td1-LT-RICM2 ****
****Laurent Mounier et Laure Gonnord ****


Exo 1 
-----

* lexicales :

C : 

	int main() {
		int 1deux = 2 ;		/* idf incorrect */
		a := a + 1 ;		/* : incorrect */
		a = a @ 2 ; 		/* @ incorrect */	
	}

Ada 

	procedure toto is 
	begin
		1deux : integer ;
		a += a % 2 ;		-- +=, % incorrects
	end ;
		
* syntaxique :

C : 

	int main() {
		int x = 2+3) ;
		x = 1 			/* pa de de ; */
		if (a) then a++ else a-- ;  /* else */
	}

Ada :

	procedure toto is 
	begin 
		x :integer ;
		x = 2 ; 	-- = au lieu de := 
		if x then x=0 ;  else x=1 ; endloop ;
	end ;  

* semantique statique :

C et Ada : 
	pbs de types : 
		expressions arithmetiques, parametres de procedures, resultats de fonctions

La difference entre C et Ada est qeu le typage est beaucoup plus fort en Ada : 

	en C : 
		typedef int T1 ;
		typedef int T2 ;
		T1 x1 ;
		T2 x2 ;
		x1 = x2 ;		/* ok */

	en Ada :

		T1 is new integer ;
		T2 is new integer ;
		x1 : T1 ;
		x2 : T2 ;
		x1 := x2 ;		/* erreur */

Ada : 
	T : array (1..5) of integer ;
	T(7) := 0 ;
	
		

* semantique dynamique :

	- operations non definies (division par zero, racine d'un nbre negatif, ...)
	- debordements de tableaux :

	   C : 
		int T[4] ; 
		T[5] = 0 ;
		int i = 8 ;
		T[i] = 0 ;

	   Ada : 
		T : array (1..5) of integer ;
		i : integer ;
		i := 6 ; 
		T(i) := 0 ;

	- acces a un fichier qui n'existe pas
	- acces a un pointeur non alloue, ou egal a NUL

En Ada les erreurs de semantique dynamique levent des exceptions (code inséré par le compilo).

Exo 2 
------

	E = ('/'.'/'*. '*'. V*.'*'.'*'*.'/')* 

Exo 3 
------

(on donne ici une solution en notation BNF)

	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
	identificateur ::= lettre.(chiffre | lettre)*


Exo 4 : 	(il y a bien sur plein d'autres solutions !)
-------

1. mots se terminant par c :	E0 = (a+b+c)*.c
	automate : 
			(0, a, 0)
			(0, b, 0)
			(0, c, 0)
			(0, c, 1)
		etats terminaux : {1}

	Rq : l'automate proposé ici est non déterministe (c'est pas génant !)
		on peut aussi le determiniser : 
			(0, a, 0)
			(0, b, 0)
			(0, c, 1)
			(1, a, 0)
			(1, b, 0)
			(1, c, 1)
		etats terminaux : {1}
		

2. mots ne se terminant pas par c : E1 = (a+b+c)*.a + (a+b+c)*.b + epsilon
	automate : on rajoute un 3eme etat pour que l'etat initial soit terminal (epsilon)

			(0, a, 1)
			(0, b, 1)
			(0, c, 2)
			(1, a, 1)
			(1, b, 1)
			(1, c, 2)
			(2, c, 2)
			(2, a, 1)
			(2, b, 1)
		etats terminaux : {0, 1}

3. nbre pair d'occurrences de "ab" ?

 - ensemble des mots contenant "au moins une" occurrence de "ab" :

		E2 = (a+b+c)*.a.b.(a+b+c)*
 
 - ensemble des mots "ne contenant pas" d'occurrence de "ab" :
	-> après un "a" on ne peut avoir qu'un "a" ou un "c"

		E3 = ((b+c)*.a.(a+c)*)*

	  automate : 
		(0, c, 0)
		(0, b, 0)
		(0, a, 1)
		(1, a, 0)
		(1, c, 0)
		(1, b, 2)
		(2, a, 2)
		(2, b, 2)
		(2, c, 2)
	etats terminaux : {0, 1} (2 est un etat "erreur").
			

 - ensemble des mots contenant "exactement une" occurrence de "ab" :

		E4 = E2.a.b.E2

- ensemble des mots contenant "un nombre pair" d'occurrences de "ab" :

		E5 = (E3.E3)*

On obtient l'automate en concatenant les automataes associes à chaque ss-expression.

4. L2 = mots qui se terminent par c
   L5 = mots qui contiennent un nbre pair d'occurrences de "ab"

   L = {m | m appartient à L2 => m appartient à L5}

   on peut ré-écrire l'implication  : 

   L = (m | m appartient a non L2 ou m appartient L5)

Comme l'union et et le complément de langages réguliers est un langage régulier 
L est régulier.

On peut caracteriser L par une expression régulière : 

		E = E2 + E5

On peut aussi faire l'union des deux automates ...