Tiêu đề °EXAMENS compilation SMI5 FSR RABAT.pdf ✅

Compilation Facult ́e des Sciences Licence Fondamentale SMI Ann ́ee 2016-2017 Evaluation TP du 07/01/2017 Nom et pr ́enom : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Code : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dur ́ee : 1 Heure 15 Minutes. Les documents manuscrits sont autoris ́es. Eteindre les t ́el ́ephones. L’usage de la calculatrice est interdit. Question 1 Soit A = (Σ, Q, δ, I, F) un automate `a ́etat fini. Donner la d ́efinition de la fonction de transition δ dans les cas suivants : 1. A est d ́eterministe : δ : ............... −→ ........... 2. A est non-d ́eterministe : δ : ............... −→ ........... Question 2 On consid`ere l’automate fini d ́eterministe A d ́efinit sur l’alphabet Σ = {a, b}, et repr ́esent ́e par le sch ́ema suivant : 1. Ecrire une fonction en langage C qui permet d’initialiser l’automate A. 2. Ecrire une fonction en langage C qui permet de tester si un mot est accept ́e par A ou non. Donner la complexit ́e temporelle de cette fonction. 3. Ecrire la fonction principale contenant un jeu de test. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .